题目传送门(BZOJ)
>原文链接<

题解 :

莫队算法主要解决的是

区间询问, 可离线,

并且在知道$[L, R]$答案的情况下, 可以快速的(一般是$O(1)$或$O(\log n)$)求出

$[L-1, R]$/$[L, R-1]$/$[L+1, R]$/$[L, R+1]$的问题.

从一个知道一个询问的答案, 到求出另一个询问的答案, 我们只需要让它的$L$和$R$一位一位挪就可以了.

秘诀就在求出答案的顺序上, 由于采用了分块的思想, 从一个询问到另一个询问, 指针跳跃的次数不会超过一个什么值(然鹅我并不会证明莫队的复杂度)

我们维护一个代表当前状态的颜色桶,

如果区间扩大, 且之前没有这个颜色, 那么当前$ans++$ ,

如果区间缩小, 且缩小之后该位置的颜色在桶里就没有了, 那么$ans –$

然后把当前$ans$赋给当前的询问即可

代码 :

#include <cmath>#include <cstdio>#include <cctype>#include <cstring>#include <algorithm>using namespace std;const int N = 510000;const int M = 1010100;int bkt[M], pos[N], a[N];int n, m, nl, nr, na, ans[N<<1];inline char nc() { static char buf[100000], *p1, *p2; return p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++;}int rd() { int x = 0;char c = nc(); while(!isdigit(c)) c = nc(); while(isdigit(c)) x=x*10+c-48, c=nc(); return x;}struct Query { int l, r, id; bool operator < (const Query x) const { if(pos[l] == pos[x.l]) return pos[l]&1?r<x.r:r>x.r; return l<x.l; }}q[N<<2];char pbuf[10000000] , *pp = pbuf;inline void write(int x) { static int sta[35]; int top = 0; if(!x)sta[++top]=0; while(x) sta[++top] = x % 10 , x /= 10; while(top)*pp++ = sta[top--]^'0';}int main() { n = rd(); for(int i = 1; i <= n; i ++ ) a[i] = rd(); int siz = sqrt(n), blk = n/siz, p = 0; for(int i = 1; i <= blk; i ++ ) for(int j = 1; j <= siz; j ++ ) pos[++p] = i; if(p < n) for(int i = p+1; i <= n; i ++ ) pos[i] = blk+1; m = rd(); for(int i = 1; i <= m; i ++ ) q[i].l = rd(), q[i].r = rd(), q[i].id = i; sort(q+1, q+m+1); for(int i = 1; i <= m; i ++ ) { while(nl<q[i].l) na -= (--bkt[a[nl++]] == 0); while(nl>q[i].l) na += (bkt[a[--nl]]++ == 0); while(nr<q[i].r) na += (bkt[a[++nr]]++ == 0); while(nr>q[i].r) na -= (--bkt[a[nr--]] == 0); ans[q[i].id] = na; } for(int i = 1; i <= m; i ++ ) write(ans[i]), *pp++='\n'; fwrite(pbuf, 1, pp-pbuf, stdout);}