题目链接：
算法一：莫队
首先，单纯的莫队算法是很好想的，就是用普通的第一关键字为 l 所在块，第二关键字为 r 的莫队。
这样每次端点移动添加或删除一个数字，用树状数组维护所求的信息就是很容易的。由于这里有 logn复杂度，所以这样移动端点的复杂度还是挺高的。
于是 BZOJ-3236 的时限 100s，我的代码跑了 98s，险过......
Paste一个BZOJ-3236的纯莫队代码：
#include#include #include #include #include #include using namespace std;inline void Read(int &Num) { char c; c = getchar(); while (c < '0' || c > '9') c = getchar(); Num = c - '0'; c = getchar(); while (c >= '0' && c <= '9') { Num = Num * 10 + c - '0'; c = getchar(); }}const int MaxN = 100000 + 5, MaxM = 1000000 + 5;int n, m, BlkSize;int A[MaxN], Cnt[MaxN], T1[MaxN], T2[MaxN];struct Query{ int l, r, a, b, Pos, e, Ans1, Ans2; Query() {} Query(int x, int y, int p, int q, int o) { l = x; r = y; a = p; b = q; Pos = o; } bool operator < (const Query &q) const { if (e == q.e) return r < q.r; return e < q.e; }} Q[MaxM];inline bool Cmp(Query q1, Query q2) { return q1.Pos < q2.Pos;}inline void Add1(int x, int Num) { for (int i = x; i <= n; i += i & -i) T1[i] += Num;}inline int Get1(int x) { if (x == 0) return 0; //Notice! int ret = 0; for (int i = x; i; i -= i & -i) ret += T1[i]; return ret;}inline void Add2(int x, int Num) { for (int i = x; i <= n; i += i & -i) T2[i] += Num;}inline int Get2(int x) { if (x == 0) return 0; //Notice! int ret = 0; for (int i = x; i; i -= i & -i) ret += T2[i]; return ret;}inline void Add_Num(int x) { if (Cnt[x] == 0) Add2(x, 1); ++Cnt[x]; Add1(x, 1);}inline void Del_Num(int x) { --Cnt[x]; Add1(x, -1); if (Cnt[x] == 0) Add2(x, -1);}void Pull(int f, int x, int y) { if (x == y) return; if (f == 0) if (x < y) for (int i = x; i < y; ++i) Del_Num(A[i]); else for (int i = x - 1; i >= y; --i) Add_Num(A[i]); else if (x < y) for (int i = x + 1; i <= y; ++i) Add_Num(A[i]); else for (int i = x; i > y; --i) Del_Num(A[i]);}int main() { Read(n); Read(m); BlkSize = (int)sqrt((double)n); for (int i = 1; i <= n; ++i) Read(A[i]); int l, r, a, b; for (int i = 1; i <= m; ++i) { Read(l); Read(r); Read(a); Read(b); Q[i] = Query(l, r, a, b, i); Q[i].e = (l - 1) / BlkSize + 1; } sort(Q + 1, Q + m + 1); memset(Cnt, 0, sizeof(Cnt)); memset(T1, 0, sizeof(T1)); memset(T2, 0, sizeof(T2)); for (int i = Q[1].l; i <= Q[1].r; ++i) Add_Num(A[i]); Q[1].Ans1 = Get1(Q[1].b) - Get1(Q[1].a - 1); Q[1].Ans2 = Get2(Q[1].b) - Get2(Q[1].a - 1); for (int i = 2; i <= m; ++i) { if (Q[i].r < Q[i - 1].l) { Pull(0, Q[i - 1].l, Q[i].l); Pull(1, Q[i - 1].r, Q[i].r); } else { Pull(1, Q[i - 1].r, Q[i].r); Pull(0, Q[i - 1].l, Q[i].l); } Q[i].Ans1 = Get1(Q[i].b) - Get1(Q[i].a - 1); Q[i].Ans2 = Get2(Q[i].b) - Get2(Q[i].a - 1); } sort(Q + 1, Q + m + 1, Cmp); for (int i = 1; i <= m; ++i) printf("%d %d\n", Q[i].Ans1, Q[i].Ans2); return 0;}
算法二：莫队+分块
这是一个神奇的做法，还是用莫队转移区间端点，但是每次移动端点都是O(1)的，不再用树状数组，而是将 [1,n] 的数值分成大小为 sqrt(n) 的块。
莫队时加入一个数，如果它之前不存在，就将它所在的块的数组值加一，删除时类似。
然后每个询问转移完区间之后用分块的方法查询答案，中间的整块直接查，两边的零散的数就暴力枚举，这样每个询问就是 sqrt(n) 的。
总复杂度也大约是 O(n^1.5) ，主要就是把移动区间端点变为了 O(1)，十分神奇！
我用这个算法写了 3809，代码如下：
#include#include #include #include #include #include using namespace std;inline void Read(int &Num) { char c; c = getchar(); while (c < '0' || c > '9') c = getchar(); Num = c - '0'; c = getchar(); while (c >= '0' && c <= '9') { Num = Num * 10 + c - '0'; c = getchar(); }}const int MaxN = 100000 + 5, MaxM = 1000000 + 5, MaxBlk = 350 + 5;int n, m, BlkSize, TotBlk;int A[MaxN], Cnt[MaxN], T[MaxBlk], L[MaxBlk], R[MaxBlk], Ans[MaxM], Blk[MaxN];struct Query{ int l, r, Index, a, b; Query() {} Query(int f, int x, int y, int p, int q) { Index = f; l = x; r = y; a = p; b = q; } bool operator < (const Query &b) const { if (Blk[l] == Blk[b.l]) return r < b.r; return Blk[l] < Blk[b.l]; }} Q[MaxM];inline void Add_Num(int x) { if (Cnt[x] == 0) ++T[Blk[x]]; ++Cnt[x];}inline void Del_Num(int x) { --Cnt[x]; if (Cnt[x] == 0) --T[Blk[x]];}void Pull(int f, int x, int y) { if (x == y) return; if (f == 0) { if (x < y) for (int i = x; i < y; ++i) Del_Num(A[i]); else for (int i = x - 1; i >= y; --i) Add_Num(A[i]); } else { if (x < y) for (int i = x + 1; i <= y; ++i) Add_Num(A[i]); else for (int i = x; i > y; --i) Del_Num(A[i]); }}int GetAns(int a, int b) { int x, y, ret; x = Blk[a]; if (L[x] != a) ++x; y = Blk[b]; if (R[y] != b) --y; ret = 0; if (x > y) { for (int i = a; i <= b; ++i) if (Cnt[i] > 0) ++ret; } else { for (int i = x; i <= y; ++i) ret += T[i]; for (int i = a; i < L[x]; ++i) if (Cnt[i] > 0) ++ret; for (int i = b; i > R[y]; --i) if (Cnt[i] > 0) ++ret; } return ret;}int main() { Read(n); Read(m); for (int i = 1; i <= n; ++i) Read(A[i]); BlkSize = (int)sqrt((double)n); TotBlk = (n - 1) / BlkSize + 1; for (int i = 1; i <= TotBlk; ++i) { L[i] = (i - 1) * BlkSize + 1; R[i] = i * BlkSize; } R[TotBlk] = n; for (int i = 1; i <= n; ++i) Blk[i] = (i - 1) / BlkSize + 1; int l, r, a, b; for (int i = 1; i <= m; ++i) { Read(l); Read(r); Read(a); Read(b); Q[i] = Query(i, l, r, a, b); } sort(Q + 1, Q + m + 1); memset(Cnt, 0, sizeof(Cnt)); memset(T, 0, sizeof(T)); for (int i = Q[1].l; i <= Q[1].r; ++i) Add_Num(A[i]); Ans[Q[1].Index] = GetAns(Q[1].a, Q[1].b); for (int i = 2; i <= m; ++i) { if (Q[i].r < Q[i - 1].l) { Pull(0, Q[i - 1].l, Q[i].l); Pull(1, Q[i - 1].r, Q[i].r); } else { Pull(1, Q[i - 1].r, Q[i].r); Pull(0, Q[i - 1].l, Q[i].l); } Ans[Q[i].Index] = GetAns(Q[i].a, Q[i].b); } for (int i = 1; i <= m; ++i) printf("%d\n", Ans[i]); return 0;}