莫队学习笔记

莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

普通莫队

设定块大小 $T$ ，将 $m$ 个询问 $[l,r]$ 离线下来，以 $(\lfloor \frac lT \rfloor, r)$ 为关键字排序后，依次处理每个询问。

时间复杂度：

若 $|l - l^\prime| + |r - r^\prime| = 1$ ，从 $[l,r]$ 转移到 $[l^\prime, r^\prime]$ 的复杂度是 $\mathcal O(1)$ 的。

整个过程中， $l$ 移动的总次数为 $\mathcal O(mT)$ ， $r$ 移动的总次数为 $\mathcal O(\frac {n^2}T)$ 。

取 $T = \frac {n}{\sqrt m}$ 时得到最优复杂度 $\mathcal O(n \sqrt m)$ ，总时间复杂度 $\mathcal O(m \log m + n \sqrt m)$ 。

注意，在 $n,m$ 同阶时，取 $T = \sqrt n$ 有最优复杂度 $\mathcal O(n \sqrt n)$ ， $1\text{s}$ 内最高可以通过 $n \le 2 \times 10^5$ 的题目。但有些毒瘤题目会把数据范围出到 $n \le 5 \times 10^4$ ， $m \le 10^6$ ，所以需要稍微注意一下 $n,m$ 不同阶的情况。

常数优化：

考虑奇偶化排序：对于 $\lfloor \frac lT \rfloor$ 为奇数的块， $r$ 从小到大排序；对于 $\lfloor \frac lT \rfloor$ 为偶数的块， $r$ 从大到小排序。

注意，排序时需要重载 <，必须符合严格弱序，即：

非自反性： $x \not< x$ 。
非对称性：若 $x < y$ ，则 $y \not< x$ 。
传递性：若 $x < y$ ， $y < z$ ，则 $x < z$ 。
不可比性的传递性：若 $x \not< y$ ， $y \not< x$ ， $y \not< z$ ， $z \not< y$ ，则 $x \not< z$ ， $z \not< x$ 。

简单来讲就是 $x < y$ 和 $y < x$ 不能同时为真。

【模板】小 Z 的袜子

const int N = 5e4 + 7;
int n, m, T, a[N], c[N];
ll ans[N], sum[N], now;
struct Q {
	int l, r, x, y, i;
	inline Q() {}
	inline Q(int l, int r, int i) : l(l), r(r), i(i) { x = l / T, y = r; }
	inline friend bool operator < (const Q &a, const Q &b) {
		return a.x == b.x ? (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
	}
} q[N];

inline void work(int x, int k) {
	x = a[x], now += k > 0 ? c[x] : 1 - c[x], c[x] += k;
}

int main() {
	rd(n, m), T = n / sqrt(m), rda(a, n);
	for (int i = 1, l, r; i <= m; i++) rd(l, r), q[i] = Q(l, r, i);
	sort(q + 1, q + m + 1);
	for (int i = 1, l = 1, r = 0; i <= m; i++) {
		while (l > q[i].l) work(--l, 1);
		while (r < q[i].r) work(++r, 1);
		while (l < q[i].l) work(l++, -1);
		while (r > q[i].r) work(r--, -1);
		ans[q[i].i] = now;
		sum[q[i].i] = 1ll * (q[i].r - q[i].l + 1) * (q[i].r - q[i].l) / 2;
	}
	for (int i = 1; i <= m; i++) {
		if (!sum[i]) {
			prints("0/1");
			continue;
		}
		ll d = __gcd(ans[i], sum[i]);
		print(ans[i] / d, '/'), print(sum[i] / d);
	}
	return 0;
}

带修莫队

增加一维时间轴，即每次询问变成 $[l,r,t]$ 。

依然设定块大小 $T$ ，然后以 $(\lfloor \frac lT \rfloor, \lfloor \frac rT \rfloor,t)$ 为关键字排序，依次处理每个询问。

时间复杂度：

若 $|l - l^\prime| + |r - r^\prime| + |t - t^\prime| = 1$ ，从 $[l,r,t]$ 转移到 $[l^\prime, r^\prime, t^\prime]$ 的复杂度是 $\mathcal O(1)$ 的。

整个过程中， $l$ 移动的总次数为 $\mathcal O(mT)$ ， $r$ 移动的总次数为 $\mathcal O(mT+ \frac {n^2}T)$ ， $t$ 移动的总次数为 $\mathcal O(\frac{n^2m}{T^2})$ 。

设 $n,m$ 同阶，取 $T = n^{\frac 23}$ 时得到最优复杂度 $\mathcal O(n^{\frac 53})$ ， $1\text{s}$ 内最高可以通过 $n \le 6 \times 10^4$ 的题目。

那如果 $n,m$ 不同阶咋办？相信我，暴力能过。

【模板】数颜色

const int N = 133337, M = 1e6 + 7;
int n, m, k, T, a[N], c[M], u[N], v[N], ans[N], now;
struct Q {
	int l, r, t, x, y, z, i;
	inline Q() {}
	inline Q(int l, int r, int t, int i) : l(l), r(r), t(t), i(i) { x = l / T, y = r / T, z = t; }
	inline friend bool operator < (const Q &a, const Q &b) {
		return a.x == b.x ? a.y == b.y ? (a.y & 1) ? a.z < b.z : a.z > b.z : (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
	}
} q[N];

inline void work(int x, int k) {
	now += k > 0 ? !c[x] : -!(c[x] - 1), c[x] += k;
}

inline void update(int i, int x) {
	if (q[i].l <= u[x] && u[x] <= q[i].r) work(a[u[x]], -1), work(v[x], 1);
	swap(a[u[x]], v[x]);
}

int main() {
	rd(n, m), T = pow(n, 2.0 / 3.0), rda(a, n);
	for (int i = 1, l, r, t = 0; i <= m; i++) {
		char o;
		rdc(o);
		if (o == 'Q') rd(l, r), ++k, q[k] = Q(l, r, t, k);
		else ++t, rd(u[t], v[t]);
	}
	sort(q + 1, q + k + 1);
	for (int i = 1, l = 1, r = 0, t = 0; i <= k; i++) {
		while (l > q[i].l) work(a[--l], 1);
		while (r < q[i].r) work(a[++r], 1);
		while (l < q[i].l) work(a[l++], -1);
		while (r > q[i].r) work(a[r--], -1);
		while (t < q[i].t) update(i, ++t);
		while (t > q[i].t) update(i, t--);
		ans[q[i].i] = now;
	}
	for (int i = 1; i <= k; i++) print(ans[i]);
	return 0;
}

回滚莫队

当删除不太容易时，可以考虑回滚莫队。

首先依然分块，对于左右两端点在同一块的询问直接暴力求答案。

其余的询问先像之前那样排序。对于相邻两块，若左端点在同一块，则右端点显然是递增的。每次处理询问时，钦定初始的左端点为当前块下一块的开头，然后先移动右端点，记录下答案后再移动左端点，询问完后还原记录下的答案。

若左端点不在同一块，则直接清空答案。这样做时间复杂度依然是 $\mathcal O(m \log m + n \sqrt m)$ 的。

【模板】历史研究

const int N = 1e5 + 7;
int n, m, T, a[N];
unordered_map<int, int> c;
ll ans[N], now;
struct Q {
	int l, r, x, y, i;
	inline Q() {}
	inline Q(int l, int r, int i) : l(l), r(r), i(i) { x = l / T, y = r; }
	inline friend bool operator < (const Q &a, const Q &b) {
		return a.x == b.x ? a.y < b.y : a.x < b.x;
	}
} q[N];
vi p;

inline void work(int x) {
	now = max(now, 1ll * x * (++c[x]));
}

int main() {
	rd(n, m), T = n / sqrt(m), rda(a, n);
	for (int i = 1, l, r; i <= m; i++) rd(l, r), q[i] = Q(l, r, i);
	sort(q + 1, q + m + 1);
	for (int i = 1, l, r; i <= m; i++) {
		if (i == 1 || q[i].x != q[i-1].x)
			l = (q[i].x + 1) * T, r = l - 1, now = 0, c.clear();
		if (q[i].x == q[i].r / T) {
			for (int j = q[i].l; j <= q[i].r; j++) work(a[j]);
			ans[q[i].i] = now;
			now = 0, c.clear();
			continue;
		}
		while (r < q[i].r) work(a[++r]);
		ll cur = now;
		while (l > q[i].l) work(a[--l]), p.pb(a[l]);
		ans[q[i].i] = now;
		l = (q[i].x + 1) * T, now = cur;
		while (p.size()) --c[p.back()], p.pop_back();
	}
	for (int i = 1; i <= m; i++) print(ans[i]);
	return 0;
}

树上莫队

首先要说明的是，树上莫队其实有两种。一种是采用王室联邦中的分块方式对树进行树分块；另一种是将树压成括号序，然后用普通/带修莫队去做。

后者与前者相比，应用上并没有什么劣势，但比前者简单许多，因此本文中只介绍后者。

树上莫队其实就是把树压成一个序列，然后用序列上莫队的方式做就好了。

那么压成什么样的序列可以符合我们的要求呢？

首先想到的肯定是 dfs 序，但压成 dfs 序之后只能处理对于子树的询问。

对于路径的询问，我们就要考虑括号序（欧拉序）了。

括号序其实就是在进入和回溯一个点时都把这个点的编号标记下来，这样可以得到一个长度为 $2n$ 的序列，同时记录点 $i$ 进入和回溯时的时间戳 $in_i, out_i$ 。

对于一次询问 $(x,y)$ ，不妨设 $in_x < in_y$ 。如果 $y$ 在 $x$ 的子树内，则直接询问括号序上的区间 $[in_x,in_y]$ ，否则询问 $[out_x,in_y]$ 。对于一次询问 $[l,r]$ ，其答案为区间中所有只出现了一次的节点对应的答案。另外，对于 $y$ 不在 $x$ 子树内的情况， $\text{LCA}(x,y)$ 并不在 $[out_x,in_y]$ 中，需要单独计算贡献。

找到哪些位置上的节点只出现了一次可以用简单的异或实现。

【模板】糖果公园

const int N = 1e5 + 7;
int n, m, cq, T, k, a[N], c[N], tx[N], ty[N];
ll v[N], w[N], ans[N], now;
vi e[N];
struct Q {
	int l, r, t, x, y, z, i, o;
	inline Q() {}
	inline Q(int l, int r, int t, int i, int o = 0) : l(l), r(r), t(t), i(i), o(o) { x = l / T, y = r / T, z = t; }
	inline friend bool operator < (const Q &a, const Q &b) {
		return a.x == b.x ? a.y == b.y ? (a.y & 1) ? a.z < b.z : a.z > b.z : (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
	}
} q[N];

namespace HLD {
	int d[N], f[N], s[N], son[N], dfn[N], rnk[N], top[N], num;
	
	void dfs(int x) {
		s[x] = 1;
		for (int y : e[x])
			if (y != f[x]) {
				f[y] = x, d[y] = d[x] + 1;
				dfs(y), s[x] += s[y];
				if (s[y] > s[son[x]]) son[x] = y;
			}
	}
	
	void dfs(int x, int p) {
		dfn[x] = ++num, rnk[num] = x;
		top[x] = p;
		if (son[x]) dfs(son[x], p);
		for (int y : e[x])
			if (y != f[x] && y != son[x])
				dfs(y, y);
	}
	
	inline int lca(int x, int y) {
		while (top[x] != top[y]) {
			if (d[top[x]] < d[top[y]]) swap(x, y);
			x = f[top[x]];
		}
		return d[x] < d[y] ? x : y;
	}
	
	inline void main() {
		d[1] = 1, dfs(1), dfs(1, 1);
	}
}
using HLD::s;
using HLD::dfn;
using HLD::lca;
using HLD::son;

int in[N], out[N], p[N<<1], r[N<<1], num;

void dfs(int x, int f) {
	in[x] = ++num, p[num] = x;
	if (son[x]) dfs(son[x], x);
	for (int y : e[x])
		if (y != f && y != son[x]) dfs(y, x);
	out[x] = ++num, p[num] = x;
} 

inline void work(int x) {
	if (r[x]) now -= v[a[x]] * w[c[a[x]]--], r[x] = 0;
	else now += v[a[x]] * w[++c[a[x]]], r[x] = 1;
}

inline void update(int i, int x) {
	if (q[i].l <= in[tx[x]] && in[tx[x]] <= q[i].r) work(tx[x]);
	if (q[i].l <= out[tx[x]] && out[tx[x]] <= q[i].r) work(tx[x]);
	swap(a[tx[x]], ty[x]);
	if (q[i].l <= in[tx[x]] && in[tx[x]] <= q[i].r) work(tx[x]);
	if (q[i].l <= out[tx[x]] && out[tx[x]] <= q[i].r) work(tx[x]);
}

int main() {
	rd(n, m, cq), T = pow(n, 2.0 / 3.0), rda(v, m), rda(w, n);
	for (int i = 1, x, y; i < n; i++) rd(x, y), e[x].pb(y), e[y].pb(x);
	rda(a, n);
	HLD::main();
	dfs(1, 0);
	for (int i = 1, o, x, y, t = 0; i <= cq; i++) {
		rd(o, x, y);
		if (o) {
			++k;
			if (dfn[x] > dfn[y]) swap(x, y);
			if (dfn[y] < dfn[x] + s[x]) q[k] = Q(in[x], in[y], t, k);
			else q[k] = Q(out[x], in[y], t, k, 1);
		} else tx[++t] = x, ty[t] = y;
	}
	sort(q + 1, q + k + 1);
	for (int i = 1, l = 1, r = 0, t = 0; i <= k; i++) {
		while (l > q[i].l) work(p[--l]);
		while (r < q[i].r) work(p[++r]);
		while (l < q[i].l) work(p[l++]);
		while (r > q[i].r) work(p[r--]);
		while (t < q[i].t) update(i, ++t);
		while (t > q[i].t) update(i, t--);
		if (q[i].o) work(lca(p[l], p[r]));
		ans[q[i].i] = now;
		if (q[i].o) work(lca(p[l], p[r]));
	}
	for (int i = 1; i <= k; i++) print(ans[i]);
	return 0;
}