莫队，永远拿不到满分的算法
longdie
2020-12-31 14:26:14
莫队是个神奇的东西。
对于普通的莫队
如果你没学过，可以提前学习一下普通莫队。
一般来说复杂度是 $O(n\sqrt n)$ 的，但是莫队是真的很难拿到满分，就算疯狂卡常，也很难拿更多的分。
但是奇偶性真的很重要，如果你不加，可能和暴力一个分，但是加上了，你就可能拿到和正解一样的分数。
好歹普通莫队还是个跟号级别的算法，比暴力还是强大不少的，但是对于带修莫队，如果你的块的大小不对，那么你的复杂度就会变成 $O(n^2)$ ,常数比暴力还大。
对于带修莫队，我们需要合理处理块的大小，使其成为 $O(n^{5/3})$, 这样的话就会优化不少，再加上奇偶性优化，就可以拿到很高的暴力分了。
插一嘴：其实带修莫队就是变成三维，新加了一维时间轴。
对于带修莫队，给个板子题[数颜色](https://www.luogu.com.cn/problem/P1903)
然后放个代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 4e4;
inline int read(int s = 0, char ch = getchar()) {
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) { s = s*10 + ch - '0'; ch = getchar(); }
return s;
}
int n, m, a[N], bk, ans[N], cnt[N*8], tmp, cntq, cntc, bel[N];
struct Q { int l, r, ti, id; } q[N];
inline bool cmp(Q a, Q b) {
if(bel[a.l] != bel[b.l]) return a.l < b.l;
if(bel[a.r] != bel[b.r]) return a.r < b.r;
return bel[a.r] & 1 ? a.ti > b.ti : a.ti < b.ti;
}
struct C { int p, co, ti; } c[N];
inline void add(int x) { if(!cnt[x]) tmp++; cnt[x]++; }
inline void del(int x) { if(cnt[x] == 1) tmp--; cnt[x]--; }
int main() {
n = read(), m = read(), bk = pow(n, 2.0/3.0);
for(register int i = 1; i <= n; ++i) a[i] = read(), bel[i] = (i-1)/bk + 1;
for(register int i = 1; i <= m; ++i) {
char op; scanf(" %c ", &op);
if(op == 'Q') q[++cntq].l = read(), q[cntq].r = read(), q[cntq].ti = cntc, q[cntq].id = cntq;
else c[++cntc].p = read(), c[cntc].co = read();
}
sort(q + 1, q + cntq + 1, cmp);
for(register int i = 1, l = 1, r = 0, ti = 0; i <= cntq; ++i) {
while(l > q[i].l) --l, add(a[l]);
while(r < q[i].r) ++r, add(a[r]);
while(l < q[i].l) del(a[l]), ++l;
while(r > q[i].r) del(a[r]), --r;
while(ti < q[i].ti) {
++ti; int pos = c[ti].p;
if(q[i].l <= pos && pos <= q[i].r) add(c[ti].co), del(a[pos]);
swap(a[pos], c[ti].co);
}
while(ti > q[i].ti) {
int pos = c[ti].p;
if(q[i].l <= pos && pos <= q[i].r) add(c[ti].co), del(a[pos]);
swap(a[pos], c[ti].co), ti--;
}
ans[q[i].id] = tmp;
}
for(register int i = 1; i <= cntq; ++i) printf("%d\n", ans[i]);
return 0;
}
```
其实带修莫队的复杂度确实有点高了，不是很好。
对于树上莫队，它的复杂度与普通莫队是一样的，复杂度很优秀，代码也很简单。
我们首先需要求出树的欧拉序，这样就可以把树转化为序列上的问题，然后对于查询的两个节点我们只需要特判他们的lca就可以了。
树上莫队最容易错的就是数组没有开大两倍，这个一定要注意呀。
下面是板子题[Count on a tree II](https://www.luogu.com.cn/problem/SP10707)的代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
inline int read(int s = 0, char ch = getchar()) {
while(!isdigit(ch)) ch = getchar();
while(isdigit(ch)) { s = s*10 +ch - '0', ch = getchar(); }
return s;
}
int n, m, a[N], b[N], head[N], cnt, bel[N], bk, tmp, ji[N], vis[N], tot, ans[N*2];
struct Q { int l, r, lca, id; } q[N];
inline bool cmp(Q a, Q b) {
if(bel[a.l] != bel[b.l]) return a.l < b.l;
return bel[a.l] & 1 ? a.r < b.r : a.r > b.r;
}
struct edge { int to, next; } e[N*2];
inline void add(int x, int y) { e[++cnt] = (edge){y, head[x]}, head[x] = cnt; }
int fir[N], lst[N], ord[N], dep[N], f[N][19];
void dfs(int u, int fa) {
ord[++tot] = u, fir[u] = tot;
for(register int i = head[u], v; i; i = e[i].next) {
if((v=e[i].to) == fa) continue;
dep[v] = dep[u] + 1, f[v][0] = u;
for(register int i = 1; (1<<i) <= dep[v]; ++i) f[v][i] = f[f[v][i-1]][i-1];
dfs(v, u);
}
ord[++tot] = u, lst[u] = tot;
}
inline int getlca(int u, int v) {
if(dep[u] < dep[v]) swap(u, v);
for(register int i = 0, d = dep[u] - dep[v]; d; d >>= 1, ++i)
if(d & 1) u = f[u][i];
if(u == v) return u;
for(register int i = 18; i >= 0; --i)
if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
inline void work(int pos) {
vis[pos] ? tmp -= !--ji[a[pos]] : tmp += !ji[a[pos]]++, vis[pos] ^= 1;
}
int main() {
n = read(), m = read();
for(register int i = 1; i <= n; ++i) b[i] = a[i] = read();
sort(b + 1, b + n + 1);
int p = unique(b + 1, b + n + 1) - b - 1;
for(register int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + p + 1, a[i]) - b;
for(register int i = 1, x, y; i < n; ++i) x = read(), y = read(), add(x, y), add(y, x);
dep[1] = 1, dfs(1, 0);
bk = sqrt(tot);
for(register int i = 1; i <= tot; ++i) bel[i] = (i-1)/bk + 1;
for(register int i = 1, l, r, lca; i <= m; ++i) {
l = read(), r = read(), lca = getlca(l, r);
if(fir[l] > fir[r]) swap(l, r);
if(l == lca) q[i].l = fir[l], q[i].r = fir[r], q[i].id = i;
else q[i].l = lst[l], q[i].r = fir[r], q[i].lca = lca, q[i].id = i;
}
sort(q + 1, q + m + 1, cmp);
for(register int i = 1, l = 1, r = 0; i <= m; ++i) {
while(l > q[i].l) work(ord[--l]);
while(r < q[i].r) work(ord[++r]);
while(l < q[i].l) work(ord[l++]);
while(r > q[i].r) work(ord[r--]);
if(q[i].lca) work(q[i].lca);
ans[q[i].id] = tmp;
if(q[i].lca) work(q[i].lca);
}
for(register int i = 1; i <= m; ++i) cout << ans[i] << '\n';
return 0;
}
```
个人感觉树上莫队比带修莫队好理解。
对于回滚莫队，其实就是对于普通莫队不是很好维护的东西，比如删除，回滚莫队其实用到了分块。
它的复杂度是很优秀的，跟普通莫队是一样的。
题目只有AT上的题，给个[链接](https://atcoder.jp/contests/joisc2014/tasks/joisc2014_c)，似乎没有题目，可以在洛谷上看。