一种用来处理序列上区间询问问题的算法。
来看一下最经典的莫队题。
区间不同数
给定长为 \(n\) 的序列 \(a\), 有 \(m\) 组询问。
每组询问给定一个区间 \([l, r]\), 求区间内有多少种不同的数。
\(n, m\le 10^5\)，\(a_i \in [0,10^6]\)
我们可以观察到如果我们已知 \([l,r]\) 的答案，是可以 \(O(1)\) 求出 \([l-1, r]\)、\([l+1, r]\)、 \([l, r-1]\)、\([l, r+1]\) 四个区间的答案的。
那么我们能否通过改变每组询问的顺序，使得总偏移量最小呢？
显然这是可以做到的，而且复杂度还比较优秀。
莫队
大致思路是将询问离线并排序，一次处理询问，暴力偏移。
至于如何排序，我们将原序列分块，设块长为 \(L\)，把所有的询问区间 \([l,r]\) 转成二元组 \((\lfloor\dfrac{1}{L}\rfloor,r)\) 由小到大排序。
我们容易发现，从区间 \([l,r]\) 转移到 \([l',r']\) 所花费的代价是 \(\left\vert l-l'\right\vert + \left\vert r-r'\right\vert\)。对于询问中的每一个块，块内的纵坐标变化最多为 \(n\)；对于每个询问，因为共有 \(\dfrac{n}{L}\) 个块，最多变化 \(L\)，每两个相邻块之间转移的复杂度为 \(O(n)\)，总复杂度为 \(O(\dfrac{n^2}{L} \times 2 + mL)\)。我们不妨另 \(n\)，\(m\) 同阶，此时取 \(L = \sqrt n\) 时有最优的时间复杂度 \(O(n\sqrt n)\)。
当然，我们还可以通过奇偶优化减少偏移量。容易发现，同一块内的询问右边界时单调递增的。此时 \(r\) 指针可以一路向右移动，于是有较高的效率。但是当询问来到下一个块时， \(r\) 指针又会回调至此时最左侧的询问右边界，且回调中不会有任何询问。那么我们考虑利用这段回调。我们把当前块内询问按右边界递减排序，从上一个块回调时就可以直接计算；下一个块按右边界递增排序， \(r\) 指针又可以直接向右移动并计算。因此，我们可以通过当前块编号的奇偶来决定排序顺序。
奇偶优化的代码：
sort(q + 1, q + m + 1, [](Query p, Query q) { return blo[p.l] < blo[q.l] || blo[p.l] == blo[q.l] && (blo[p.l] & 1 ? p.r < q.r : p.r > q.r);});
// 先按照不同的块分，如果块相同，则按照块的编号奇偶来确定递增还是递减
回到本题，我们只需要在每次偏移时 \(O(1)\) 处理好添加一个数和删去一个数的操作就好了。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 1e6 + 3;
struct Query {
int l, r, id; // 询问的区间，询问编号
} q[kmax];
int c[kmax], n, m, a[kmax];
int block, blo[kmax];
long long res[kmax], o; // o 记录的是种类数
void Add(int x) {
o += (++c[x] == 1); // 添加操作，如果当前数是第一次添加，种类数+1
}
void Del(int x) {
o -= (--c[x] == 0); //删除操作，如果当前数是最后一个，种类数-1
}
int main() {
scanf("%d", &n);
block = sqrt(n); // 块长
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
blo[i] = (i - 1) / block + 1; // 算出每个下标属于哪个块
}
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
// 奇偶优化排序
sort(q + 1, q + m + 1, [](Query p, Query q) { return blo[p.l] < blo[q.l] || blo[p.l] == blo[q.l] && (blo[p.l] & 1 ? p.r < q.r : p.r > q.r); });
for (int i = 1, l = 1, r = 0; i <= m; i++) {
for (; l > q[i].l; Add(a[--l])) { // 区间左端点在 l 左边，说明要加数。先将 l 指针向左移动，再加数。
}
for (; r < q[i].r; Add(a[++r])) { // 区间右端点在 r 右边，说明要加数。先将 r 指针向右移动，再加数。
}
for (; l < q[i].l; Del(a[l++])) { // 区间左端点在 l 右边，说明要删数。先删去 l 指针位置的数，再向右移动。
}
for (; r > q[i].r; Del(a[r--])) { // 区间右端点在 r 左边，说明要删数。先删去 r 指针位置的数，再向左移动。
}
res[q[i].id] = o; // 记录答案
}
for (int i = 1; i <= m; i++) {
printf("%lld\n", res[i]); // 输出
}
return 0;
}
看一下其他题目。
区间mex
有一个长度为 \(n\) 的数组 \({a_1,a_2,...,a_n}\) 和 \(m\) 次询问。每次询问一个区间内最小没有出现过的自然数。
\(n，m \leq 2\times 10^5，a_i \in [0,10^9]， 1\leq l< r\leq n\)
每次修改的时间是 \(O(\sqrt n)\) 的，显然我们不能再往上面堆时间。但我们发现查询是 \(O(1)\)，所以我们可以牺牲一点查询的时间。
考虑分块，对每个块记录长度和块内出现的数的种类数。查询时扫描每个块，如果块内种类数 \(<\) 块长。说明当前查询的 \(mex\) 值在该块中，暴力扫块内每个数判断即可。
可能需要一点输入输出优化，时间复杂度 \(O(n\sqrt n)\)。
代码：
#pragma GCC optimize(3, "Ofast", "inline")
#pragma GCC optimize(2)
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 4e5 + 3;
struct Query {
int l, r, id;
} q[kmax];
int n, m, a[kmax];
int c[kmax];
int block, blo[kmax], bc[kmax];
int ct[kmax];
int res[kmax], o;
void Add(int x) {
if (++c[x] == 1) { // 当前数首次添加，所在块的种类数+1
ct[blo[x]]++;
}
}
void Del(int x) {
if (--c[x] == 0) { // 当前数是最后一次删除，所在块的种类数-1
ct[blo[x]]--;
}
}
int Calc() {
for (int i = 1; i <= blo[n]; i++) { // 扫描每个块
if (ct[i] == bc[i]) continue; // 当前块内所有数都出现了，跳过
// 否则暴力判断块中每个数
for (int j = (i - 1) * block; j <= min(n, i * block - 1); j++) {
if (!c[j]) return j; // 当前数未出现过，计为答案
}
}
return 0;
}
int read() {
int x = 0;
bool f = 1;
char c;
for (c = getchar(); c < '0' || c > '9'; c = getchar()) {
if (c == '-') f = 0;
}
for (; c >= '0' && c <= '9'; c = getchar()) {
x = (x << 1) + (x << 3) + (c ^ 48);
}
return f ? x : -x;
}
void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x >= 10) {
write(x / 10);
}
putchar(x % 10 + 48);
}
int main() {
n = read(), m = read();
block = sqrt(n);
blo[0] = 1;
for (int i = 1; i <= n; i++) {
a[i] = read();
if (a[i] >= kmax) a[i] = kmax - 1; // 因为只有 n 个数，所以 mex 值不会很大，我们可以把大数改为小数，方便数组记录，也不会影响结果
blo[i] = i / block + 1;
}
for (int i = 1; i <= blo[n]; i++) {
bc[i] = min(n, i * block - 1) - (i - 1) * block + 1; // 记录块长
}
for (int i = 1; i <= m; i++) {
q[i].l = read(), q[i].r = read();
q[i].id = i;
}
// 正常的莫队操作
sort(q + 1, q + m + 1, [](Query p, Query q) { return blo[p.l] < blo[q.l] || blo[p.l] == blo[q.l] && (blo[p.l] & 1 ? p.r < q.r : p.r > q.r); });
for (int i = 1, l = 1, r = 0; i <= m; i++) {
for (; l > q[i].l; Add(a[--l])) {
}
for (; r < q[i].r; Add(a[++r])) {
}
for (; l < q[i].l; Del(a[l++])) {
}
for (; r > q[i].r; Del(a[r--])) {
}
res[q[i].id] = Calc(); // 查询答案
}
for (int i = 1; i <= m; i++) {
write(res[i]);
puts("");
}
return 0;
}
[国家集训队] 数颜色 / 维护队列
此题在普通莫队上加入了修改操作。
我们给每组询问再添一一个值 \(p\)，表示再次询问前有多少次修改。在偏移指针的时候，我们同时偏移时间指针。
假如我们当前修改的次数为 \(x\)，当前询问的修改次数为 \(y\)。若 \(x < y\)， 那么我们需要将 \(x+1\) 到 \(y\) 的询问暴力添加；若 \(x>y\)，我们则要将 \(x-1\) 到 \(y\) 的询问添加。
for (; p < q[i].t; Update(++p)) {
}
for (; p > q[i].t; Update(p--)) {
}
我们还是同样的，将修改操作 \(O(1)\) 的添加和删除，同时维护好答案。
修改的时候，我们将原数值与修改后的值交换，这样撤回的时候再次交换即可，可以简便实现。
但是直接修改可能会有问题。如果修改的位置在当前询问区间 \([l,r]\) 中，那么我们需要删除原数再添加，否则直接修改即可。
void Update(int x) { // 第x个修改
if (l <= g[x].p && g[x].p <= r) { // 在区间内
Add(g[x].c); // 添加
Del(a[g[x].p]); // 删除
}
swap(g[x].c, a[g[x].p]); //交换
}
此外，在排序的时候，我们将 \(l\) 所在的块为第一关键字， \(r\) 所在的块为第二关键字，最后以 \(p\) 为第三关键字奇偶排序。如果不将 \(r\) 分块，那么乱序的右端点对于每个询问会移动 \(n\) 次，并且有序的右端点会带来乱序的时间，每次询问会移动 \(p\) 次。
bool Comp(Query p, Query q) {
if (blo[p.l] ^ blo[q.l]) return p.l < q.l;
if (blo[p.r] ^ blo[q.r]) return p.r < q.r;
return blo[p.r] & 1 ? p.t < q.t : p.t > q.t;
}
考虑询问中的每一个小块，小块内的每个询问的一二关键字相同。在此块内显然 \(p\) 最多变化 \(m\)，对于每个询问 \(l，r\) 最多变化块长 \(S_1\) 和 \(S_2\)，共 \(\dfrac{n^2}{S_1S_2}\) 个块，相邻块间的转移是 \(O(n)\) 的。总复杂度是 \(O(m(S_1+S_2) + \dfrac{n^2m}{S_1S_2} + \dfrac{n^2}{S_1S_2})\)，令 \(n，m\) 同阶， 取 \(S_1 =S_2=n^{\tfrac{2}{3}}\) 时有最优复杂度 \(O(n^{\tfrac{5}{3}})\)。
本题代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 1e6 + 3;
int n, m;
int l = 1, r, p, o;
int a[kmax], c[kmax];
int ct, cct;
int blo[kmax];
int res[kmax];
char op[3];
struct Query {
int l, r, t, id;
} q[kmax];
struct Color {
int p, c;
} g[kmax];
bool Comp(Query p, Query q) {
if (blo[p.l] ^ blo[q.l]) return p.l < q.l;
if (blo[p.r] ^ blo[q.r]) return p.r < q.r;
return blo[p.r] & 1 ? p.t < q.t : p.t > q.t; // 根据时间奇偶排序
}
void Add(int x) {
o += (++c[x] == 1);
}
void Del(int x) {
o -= (--c[x] == 0);
}
void Update(int x) {
if (l <= g[x].p && g[x].p <= r) { // 在区间内
Add(g[x].c);
Del(a[g[x].p]);
}
swap(g[x].c, a[g[x].p]); // 交换
}
int main() {
scanf("%d %d", &n, &m);
int block = ceil(pow(n, 2.0 / 3.0)); // 取2/3次方
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
blo[i] = (i - 1) / block + 1; // 求块
}
for (int i = 1, x, y; i <= m; i++) { // 两种操作分开记录
scanf("%s %d %d", op, &x, &y);
if (op[0] == 'Q') {
q[++ct] = {x, y, cct};
q[ct].id = ct;
} else {
g[++cct] = {x, y};
}
}
sort(q + 1, q + ct + 1, Comp);
for (int i = 1; i <= ct; i++) {
for (; l < q[i].l; Del(a[l++])) {
}
for (; l > q[i].l; Add(a[--l])) {
}
for (; r < q[i].r; Add(a[++r])) {
}
for (; r > q[i].r; Del(a[r--])) {
}
for (; p < q[i].t; Update(++p)) { // 时间的偏移
}
for (; p > q[i].t; Update(p--)) {
}
res[q[i].id] = o;
}
for (int i = 1; i <= ct; i++) {
printf("%d\n", res[i]);
}
return 0;
}
Machine Learning
首先我们观察到，如果 \(mex\) 值是 \(m\)，说明对于 \(\forall i \in [1,m)\)，\(\exists j\) 满足 \(j\) 出现了 \(i\) 次。总共就有至少 \(\dfrac{m(m+1)}{2}\) 个数。又因为 \(\dfrac{m(m+1)}{2} \le n\)，所以 \(m\) 是在 \(\sqrt n\) 这一量级的。也就是说我们查询答案的时候可以暴力枚举。
添加或删除的时候，假设当前数 \(x\) 出现了 \(p_x\) 次。那只需将 \(c_{p_x}-1，c_{p_x\pm 1}+1\) 即可。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int kmax = 2e5 + 3;
struct Q {
int l, r, t, id;
} q[kmax];
struct C {
int x, c;
} v[kmax];
int n, m, a[kmax], b[kmax], len;
int block, blo[kmax];
int c[kmax], p[kmax];
int qc, vc;
int l = 1, r, t;
int res[kmax];
void Add(int x) {
c[p[x]]--;
c[++p[x]]++;
}
void Del(int x) {
c[p[x]]--;
c[--p[x]]++;
}
void Update(int x) {
if (l <= v[x].x && v[x].x <= r) {
Add(v[x].c);
Del(a[v[x].x]);
}
swap(v[x].c, a[v[x].x]);
}
int main() {
scanf("%d%d", &n, &m);
block = ceil(pow(n, 2.0 / 3.0));
len = n;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[i] = a[i];
blo[i] = (i - 1) / block + 1;
}
for (int i = 1, op, x, y; i <= m; i++) {
scanf("%d%d%d", &op, &x, &y);
if (op == 1) {
qc++;
q[qc] = {x, y, vc, qc};
} else {
v[++vc] = {x, y};
b[++len] = y;
}
}
sort(q + 1, q + qc + 1, [](Q p, Q q) { return blo[p.l] != blo[q.l] ? p.l < q.l : (blo[p.r] != blo[q.r] ? p.r < q.r : (blo[p.r] & 1 ? p.t < q.t : p.t > q.t)); });
sort(b + 1, b + len + 1);
len = unique(b + 1, b + len + 1) - b - 1;
for (int i = 1; i <= n; i++) {
a[i] = lower_bound(b + 1, b + len + 1, a[i]) - b;
}
for (int i = 1; i <= vc; i++) {
v[i].c = lower_bound(b + 1, b + len + 1, v[i].c) - b;
}
for (int i = 1; i <= qc; i++) {
for (; t < q[i].t; Update(++t)) {
}
for (; t > q[i].t; Update(t--)) {
}
for (; l > q[i].l; Add(a[--l])) {
}
for (; r < q[i].r; Add(a[++r])) {
}
for (; l < q[i].l; Del(a[l++])) {
}
for (; r > q[i].r; Del(a[r--])) {
}
for (res[q[i].id] = 1; c[res[q[i].id]]; res[q[i].id]++) {
}
}
for (int i = 1; i <= qc; i++) {
printf("%d\n", res[i]);
}
return 0;
}
树上路径颜色数量
给定一棵 \(n\) 个结点的树，每个节点上有一个颜色 \(c_i\)。
有 \(m\) 次询问，每次求树上从 \(x\) 到 \(y\) 结点最短路径上颜色种类数。
\(1\le n，m\le 10^5\)，\(1\le c_i \le n\)
树上莫队
我们尝试将整棵树转化成一个序列，再在序列上做莫队。
对于这样一棵树，它的DFS括号序列是:
\(1,2,7,7,9,9,2,3,4,8,8,4,5,5,6,6,3,1\)
我们发现这个序列中每个数恰好出现了2次。我们将一个数第一次出现的地方记为 \(l\)，第二次出现的地方记为 \(r\)。
考虑树上的一条简单路径 \((x,y)\) (\(d_x < d_y\))，记 \(l\) 为 \(Lca(x, y)\)。那么我们发现：
-
若 \(x = l\)，则路径 \((x,y)\) 经过的点为区间 \([l_x,l_y]\) 中仅出现一次的点。
如： \((3,5) \rightarrow 3,4,8,8,4,5 \rightarrow 3,5\)
-
若 \(x \neq l\)，则路径 \((x,y)\) 经过的点为区间 \([r_x,l_y]\) 中仅出现一次的点和 \(l\)。
如： \((9,6) \rightarrow 9,2,3,4,8,8,4,5,5,6\rightarrow 9,2,3,6,1(Lca)\)
那就很好处理了，将每组询问转成区间，做普通莫队即可。
观察到每个点只有两种状态，在路径上或者不在路径上。用一个 \(bool\) 值 记录，每次修改时判断是添加还是删除就可以了。
至于为什么是用DFS括号序列而不是DFS序列，原因是DFS序列中每个元素仅出现一次，不太好处理一个点是否在区间内。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int kmax = 2e5 + 3; // 空间开两倍
const int kmaxM = 23;
struct Q {
int l, r, lca;
int id;
} q[kmax];
int n, m, col[kmax];
int c[kmax];
int block, blo[kmax];
int in[kmax], out[kmax], num[kmax], idx;
int d[kmax], f[kmax][kmaxM];
int s[kmax], res[kmax], ct;
bool o[kmax];
vector<int> e[kmax];
void Dfs(int x, int fa) {
d[x] = d[fa] + 1;
f[x][0] = fa;
in[x] = ++idx; // 记录进入子树时间
num[idx] = x;
for (int i = 1; i < kmaxM; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int y : e[x]) {
if (y == fa) continue;
Dfs(y, x);
}
out[x] = ++idx; // 记录离开子树时间
num[idx] = x;
}
int Lca(int x, int y) {
if (d[x] > d[y]) swap(x, y);
for (int i = kmaxM - 1; i >= 0; i--) {
if (d[f[y][i]] >= d[x]) {
y = f[y][i];
}
}
for (int i = kmaxM - 1; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return x == y ? x : f[x][0];
}
void Add(int x) {
if (++c[x] == 1) ct++;
}
void Del(int x) {
if (--c[x] == 0) ct--;
}
void Modify(int x) {
if (!o[x]) { // 判断
Add(col[x]);
} else {
Del(col[x]);
}
o[x] = !o[x]; // 状态改变
}
int main() {
scanf("%d%d", &n, &m);
block = sqrt(n);
for (int i = 1; i <= n; i++) {
scanf("%d", &col[i]);
}
for (int i = 1; i <= n << 1; i++) {
blo[i] = (i - 1) / block + 1;
}
for (int i = 1, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
e[x].push_back(y);
e[y].push_back(x);
}
Dfs(1, 0);
for (int i = 1; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
if (in[q[i].l] > in[q[i].r]) swap(q[i].l, q[i].r);
int l = Lca(q[i].l, q[i].r);
if (l == q[i].l) { // 如果是lca
q[i] = {in[q[i].l], in[q[i].r], 0, i};
} else { // 不是lca
q[i] = {out[q[i].l], in[q[i].r], l, i};
}
}
sort(q + 1, q + m + 1, [](Q p, Q q) { return blo[p.l] < blo[q.l] || blo[p.l] == blo[q.l] && (blo[p.l] & 1 ? p.r < q.r : p.r > q.r); });
for (int i = 1, l = 1, r = 0; i <= m; i++) {
for (; l > q[i].l; Modify(num[--l])) {
}
for (; r < q[i].r; Modify(num[++r])) {
}
for (; l < q[i].l; Modify(num[l++])) {
}
for (; r > q[i].r; Modify(num[r--])) {
}
if (q[i].lca) Modify(q[i].lca); // 单独处理
res[q[i].id] = ct;
if (q[i].lca) Modify(q[i].lca); // 记得删除
}
for (int i = 1; i <= m; i++) {
printf("%d\n", res[i]);
}
return 0;
}
树上带修路径询问
给定一棵 \(n\) 个节点的树，共有 \(m\) 次操作，操作分为两种：
1, x, y: 表示把第 \(x\) 的节点权值改为 \(y\)。2, x, y: 令 \(s\) 表示每一种从 \(x\) 号节点到 \(y\) 号节点出现的权值的次数，输出 \(\sum\dfrac{s(s+1)}{2}\)。
同理，将树转为序列处理，使用带修莫队，注意答案统计的内容。
代码：
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int kmax = 2e5 + 3;
const int kmaxM = 23;
struct E {
int p, y;
} e[kmax << 1];
struct T {
int x, v;
} t[kmax];
struct Q {
int l, r, lca, t;
int id;
} q[kmax];
int n, m, col[kmax];
int l = 1, r = 0, p = 0;
int tc, qc;
int c[kmax];
int h[kmax], ec;
int block, blo[kmax];
int in[kmax], out[kmax], num[kmax], idx;
int d[kmax], f[kmax][kmaxM];
long long s[kmax], res[kmax], ct;
bool o[kmax];
void Addedge(int x, int y) {
e[++ec] = {h[x], y};
h[x] = ec;
}
void Dfs(int x, int fa) {
d[x] = d[fa] + 1;
f[x][0] = fa;
in[x] = ++idx;
num[idx] = x;
for (int i = 1; i < kmaxM; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int i = h[x]; i; i = e[i].p) {
int y = e[i].y;
if (y == fa) continue;
Dfs(y, x);
}
out[x] = ++idx;
num[idx] = x;
}
int Lca(int x, int y) {
if (d[x] > d[y]) swap(x, y);
for (int i = kmaxM - 1; i >= 0; i--) {
if (d[f[y][i]] >= d[x]) {
y = f[y][i];
}
}
for (int i = kmaxM - 1; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return x == y ? x : f[x][0];
}
// 统计答案，先减再改最后加
void Add(int x) {
ct -= 1ll * c[x] * (c[x] - 1) / 2;
c[x]++;
ct += 1ll * c[x] * (c[x] - 1) / 2;
}
void Del(int x) {
ct -= 1ll * c[x] * (c[x] - 1) / 2;
c[x]--;
ct += 1ll * c[x] * (c[x] - 1) / 2;
}
void Modify(int x) {
if (!o[x]) {
Add(col[x]);
} else {
Del(col[x]);
}
o[x] = !o[x];
}
void Update(int x) {
if (o[t[x].x]) {
Add(t[x].v);
Del(col[t[x].x]);
}
swap(t[x].v, col[t[x].x]);
}
bool Comp(Q p, Q q) {
if (blo[p.l] ^ blo[q.l])
return p.l < q.l;
if (blo[p.r] ^ blo[q.r])
return p.r < q.r;
return blo[p.r] & 1 ? p.t < q.t : p.t > q.t;
}
int main() {
scanf("%d%d", &n, &m);
block = pow(n * 2, 2.0 / 3);
for (int i = 1; i <= n; i++) {
scanf("%d", &col[i]);
}
for (int i = 1; i <= n << 1; i++) {
blo[i] = (i - 1) / block + 1;
}
for (int i = 1, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
x++, y++;
Addedge(x, y);
Addedge(y, x);
}
Dfs(1, 0);
for (int i = 1, op; i <= m; i++) {
scanf("%d", &op);
if (op == 1) {
tc++;
scanf("%d%d", &t[tc].x, &t[tc].v);
t[tc].x++;
} else {
qc++;
scanf("%d%d", &q[qc].l, &q[qc].r);
q[qc].l++, q[qc].r++;
if (in[q[qc].l] > in[q[qc].r]) swap(q[qc].l, q[qc].r);
int l = Lca(q[qc].l, q[qc].r);
if (l == q[qc].l) {
q[qc] = {in[q[qc].l], in[q[qc].r], 0, tc, qc};
} else {
q[qc] = {out[q[qc].l], in[q[qc].r], l, tc, qc};
}
}
}
sort(q + 1, q + qc + 1, Comp);
for (int i = 1; i <= qc; i++) {
for (; l > q[i].l; Modify(num[--l])) {
}
for (; r < q[i].r; Modify(num[++r])) {
}
for (; l < q[i].l; Modify(num[l++])) {
}
for (; r > q[i].r; Modify(num[r--])) {
}
for (; p < q[i].t; Update(++p)) {
}
for (; p > q[i].t; Update(p--)) {
}
if (q[i].lca) Modify(q[i].lca);
res[q[i].id] = ct;
if (q[i].lca) Modify(q[i].lca);
}
for (int i = 1; i <= qc; i++) {
printf("%lld\n", res[i]);
}
return 0;
}
Haruna’s Breakfast
树上带修路径求 \(mex\)。
在此不再阐述思路，详情请结合前文所述。
实在不知道为什么我暴力查答案可以过。。。。。。
代码：（暴力查询）
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int kmax = 2e5 + 3;
const int kmaxM = 23;
struct E {
int p, y;
} e[kmax << 1];
struct T {
int x, v;
} t[kmax];
struct Q {
int l, r, lca, t;
int id;
} q[kmax];
int n, m, col[kmax];
int l = 1, r = 0, p = 0;
int tc, qc;
int c[kmax];
int h[kmax], ec;
int block, blo[kmax];
int in[kmax], out[kmax], num[kmax], idx;
int d[kmax], f[kmax][kmaxM];
long long s[kmax], res[kmax];
bool o[kmax];
void Addedge(int x, int y) {
e[++ec] = {h[x], y};
h[x] = ec;
}
void Dfs(int x, int fa) {
d[x] = d[fa] + 1;
f[x][0] = fa;
in[x] = ++idx;
num[idx] = x;
for (int i = 1; i < kmaxM; i++) {
f[x][i] = f[f[x][i - 1]][i - 1];
}
for (int i = h[x]; i; i = e[i].p) {
int y = e[i].y;
if (y == fa) continue;
Dfs(y, x);
}
out[x] = ++idx;
num[idx] = x;
}
int Lca(int x, int y) {
if (d[x] > d[y]) swap(x, y);
for (int i = kmaxM - 1; i >= 0; i--) {
if (d[f[y][i]] >= d[x]) {
y = f[y][i];
}
}
for (int i = kmaxM - 1; i >= 0; i--) {
if (f[x][i] != f[y][i]) {
x = f[x][i];
y = f[y][i];
}
}
return x == y ? x : f[x][0];
}
void Add(int x) {
c[x]++; // 直接加
}
void Del(int x) {
c[x]--; // 直接减
}
void Modify(int x) {
if (!o[x]) {
Add(col[x]);
} else {
Del(col[x]);
}
o[x] = !o[x];
}
void Update(int x) {
if (o[t[x].x]) {
Add(t[x].v);
Del(col[t[x].x]);
}
swap(t[x].v, col[t[x].x]);
}
bool Comp(Q p, Q q) {
if (blo[p.l] ^ blo[q.l])
return p.l < q.l;
if (blo[p.r] ^ blo[q.r])
return p.r < q.r;
return p.t < q.t;
}
int main() {
scanf("%d%d", &n, &m);
block = sqrt(n);
for (int i = 1; i <= n; i++) {
scanf("%d", &col[i]);
if (col[i] >= n + 2) col[i] = n + 2; // 太大的没必要
}
blo[0] = 1;
for (int i = 1; i <= n; i++) {
blo[i] = (i - 1) / block + 1;
}
for (int i = 1, x, y; i < n; i++) {
scanf("%d%d", &x, &y);
Addedge(x, y);
Addedge(y, x);
}
Dfs(1, 0);
for (int i = 1, op; i <= m; i++) {
scanf("%d", &op);
if (op == 0) {
tc++;
scanf("%d%d", &t[tc].x, &t[tc].v);
t[tc].v = min(t[tc].v, n + 2);
} else {
qc++;
scanf("%d%d", &q[qc].l, &q[qc].r);
if (in[q[qc].l] > in[q[qc].r]) swap(q[qc].l, q[qc].r);
int l = Lca(q[qc].l, q[qc].r);
if (l == q[qc].l) {
q[qc] = {in[q[qc].l], in[q[qc].r], 0, tc, qc};
} else {
q[qc] = {out[q[qc].l], in[q[qc].r], l, tc, qc};
}
}
}
sort(q + 1, q + qc + 1, Comp);
for (int i = 1; i <= qc; i++) {
for (; l > q[i].l; Modify(num[--l])) {
}
for (; r < q[i].r; Modify(num[++r])) {
}
for (; l < q[i].l; Modify(num[l++])) {
}
for (; r > q[i].r; Modify(num[r--])) {
}
for (; p < q[i].t; Update(++p)) {
}
for (; p > q[i].t; Update(p--)) {
}
if (q[i].lca) Modify(q[i].lca);
for (res[q[i].id] = 0; c[res[q[i].id]]; res[q[i].id]++) { // 这里暴力查询
}
if (q[i].lca) Modify(q[i].lca);
}
for (int i = 1; i <= qc; i++) {
printf("%lld\n", res[i]);
}
return 0;
}
完结撒花 \ / \ / \ /
标签：int,++,--,blo,kmax,include,莫队 From： https://www.cnblogs.com/ereoth/p/17364120.html