「莫队」学习笔记

前言

其实莫队很早之前就已经学会了,但是出于某些原因,并没有写好一篇完整的博客。

现在来补坑。

关于莫队

这是国家队队长莫涛发明出来的算法,在国际算法界有很高的地位。

关于莫队算法,我们都知道是一个离线算法。

所谓离线算法,就是我们把所有的处理全部都记录下来后,一起操作得到答案。

算法思路

莫队一个非常优美的暴力统计算法。

首先我们把所有区间操作都记录下来后,我们对于询问分块,按照左端点所在区间的块排序,如果相同,那么就按照右端点的位置排序。

然后我们就可以暴力统计了,我们维护两个指针,记录当前我们已经知道了$[l,r]$区间内的答案。

然后我们用这样方法移动指针。

for (int i = 1; i <= Q; i ++) {
  while (l < q[i].l) dec(l ++); 
  while (l > q[i].l) inc(-- l);
  while (r < q[i].r) inc(++ r);
  while (r > q[i].r) dec(r --);
  ans[q[i].id] = res;
}

我们分析一下复杂度,每一次我们移动指针的大小在$\sqrt n$以内,所以我们算法的复杂度为$O(n\times \sqrt n)$。

例题

题目链接:SPOJ 3267

典型的莫队模板。

每次移动指针的时候判断一下区间内的桶的大小并且更新即可。

Code

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define REP(i, s, t) for (int i = (s), i##ed = (t); i <= i##ed; i ++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
template <typename T> void chkmax(T &x, T y) {
  x = x > y ? x : y;
}
template <typename T> void chkmin(T &x, T y) {
  x = x < y ? x : y;
}
template <typename T> void read(T &x) {
  x = 0; bool w = 0; char ch = 0;
  for (; !isdigit(ch); ch = getchar()) w |= ch == '-';
  for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
  x *= w ? -1 : 1;
}
template <typename T> void write(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
template <typename T> void write(T x, char ch) {
  write(x);
  putchar(ch);
}
template <typename T> void writeln(T x) {
  write(x);
  puts("");
}
const int N = 200000 + 5;
const int M = 1e6 + 5;
struct ques {
  int l, r, id;
} q[M];
int n, Q, res;
int a[N], cnt[M], ans[N];
void inc(int cur) {
  res += (cnt[a[cur]] ++ == 0); 
}
void dec(int cur) {
  res -= (-- cnt[a[cur]] == 0);
}
int main() {
  memset(cnt, 0, sizeof(cnt));
  read(n);
  for (int i = 1; i <= n; i ++) {
    read(a[i]);
  }
  read(Q); 
  int ques_block_sz = sqrt(n);
  for (int i = 1; i <= Q; i ++) {
    read(q[i].l); read(q[i].r);
    q[i].id = i;
  }
  sort(q + 1, q + 1 + Q, [&](ques a, ques b){ return a.l / ques_block_sz == b.l / ques_block_sz ? a.r < b.r : a.l < b.l; });
  int l = 1, r = 0;
  res = 0;
  for (int i = 1; i <= Q; i ++) {
    while (l < q[i].l) dec(l ++); 
    while (l > q[i].l) inc(-- l);
    while (r < q[i].r) inc(++ r);
    while (r > q[i].r) dec(r --);
    ans[q[i].id] = res;
  }
  for (int i = 1; i <= Q; i ++) {
    writeln(ans[i]);
  }
  return 0; 
}

后记

待修莫队和树上莫队等我有时间在写好了QAQ。

最后修改:2019 年 08 月 10 日 09 : 40 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论