P7710 [Ynoi2077] stdmxeypz 题解
我的第一道 Ynoi 题，体验感不高，调了大半天，最后发现有个地方 \(B_1\) 写成 \(B_2\) 了。
分析
树上问题，明显是要转到树下的，所以 DFS 序是一定要求的。
有关树上距离，所以 \(deep\) 数组也是一定要求的。
所以我们现在把问题转化成了：
给你三个序列 \(dfn, deep, val\)，支持两个操作：
-
对于所有的 \(dfn_i \in [l, r]\) 且 \(deep_i \bmod x = y\)，令 \(val_i\) 加上 \(z\)；
-
求 \(val_i\) 的值。
有取模，应该不难想到根号分治。或者如果你做了 P5309 [Ynoi2011] 初始化，也能一眼看出来是根号分治，那个题就是这个题的序列版。
题解
先声明几个东西：
-
算复杂度时认为 \(n, m\) 同阶。
-
\(dfn_i\) 表示 \(i\) 的 DFS 序；
-
\(deep_i\) 表示 \(dfn = i\) 的点的深度；
-
\(val_i\) 表示 \(dfn = i\) 的点的权值；
-
\(l_i\) 表示以 \(i\) 为根的子树里最小的 \(dfn\)，其实就是它自身的 \(dfn\)；
-
\(r_i\) 表示以 \(i\) 为根的子树里最大的 \(dfn\)，其实就是 \(l_i + size_i - 1\)；
-
\(y\) 与给出的 \(y\) 不同。当给出操作一时，因为我们要找一些 \(i\) 使 \((deep_i - deep_{dfn_v}) \bmod x = y\)，所以我们设 \(y = (deep_{dfn_v} + y) \bmod x\)。
既然是根号分治，我们得想分治什么。这个题比较明显了，既然是对 \(x\) 取模，那肯定分治 \(x\)。
所以设一个阈值 \(B_1\)，将第一种操作再分成两类，\(x\) 小于等于 \(B_1\) 的分为一类，大于 \(B_1\) 的分为一类。
我们考虑怎么处理这两类操作。
先考虑小于 \(B_1\) 的，感觉这一部分比较好想。
考虑一下我们需要枚举什么、有什么限制：
-
我们需要从 \(l\) 到 \(r\) 枚举一个 \(i\)；
-
当 \(deep_i \bmod x = y\) 时，使 \(val_i\) 加上 \(z\)。
所以我们可以设一个 \(f_{i, j, k}\) 表示 \(dfn = i\) 的点的深度 \(\bmod j = k\) 时需要让它的权值加上多少。
这样单次修改是 \(O(n)\) 的，单次查询是 \(O(1)\) 的，且空间复杂度为 \(O(n^2)\)，一共要修改 \(m\) 次，查询 \(m \sqrt n\) 次，明显不行。
所以序列分块一下，\(f_{i, j, k}\) 表示 \(dfn\) 在第 \(i\) 个块内且深度 \(\bmod x = y\) 的点的权值需要加多少。单次修改 \(O(\sqrt n)\)，单次查询 \(O(\sqrt n)\)，空间复杂度 \(O(n \sqrt n)\)，调调块长能过。
然后再来考虑大于 \(B_2\) 的操作。
我们先把每一个点看做二维的，坐标为 \((deep_{dfn_i}, dfn_i)\)。
因为模数大于阈值，所以考虑直接暴跳，最多暴跳 \(\displaystyle \frac{n}{B_1}\) 次。跳到每一个 \(deep\)，直接暴力修改这一深度下 \(dfn\) 在 \([l, r]\) 区间内的点。
这样单次修改是 \(O(n)\) 的，单次查询是 \(O(1)\) 的，且空间复杂度为 \(O(n^2)\)，一共要修改 \(m \sqrt n\) 次，查询 \(m\) 次，明显不行。
所以考虑序列差分分块，数组 \(\sum_{k = 1}^j cha_{i, k}\) 表示深度为 \(i\) 且 \(dfn\) 在第 \(j\) 个块内的点，权值需要加上多少。单次修改 \(O(1)\)，单次查询 \(O(\sqrt n)\)，空间复杂度 \(O(n \sqrt n)\)，调调块长能过。
阈值 \(B_1\) 设到 \(\sqrt n\) 左右，块长 \(B_2\) 设到 \(2000\) 左右（或者说你需要保证 \(O(\frac{n^2}{B_2})\) 的空间复杂度能过），并不觉得卡常。
代码
#include <bits/stdc++.h>
#define M 300005
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
const int B1 = 500, B2 = 2000;
int n, q, tim, ld[M], rd[M], deep[M], maxdeep;
int to[M << 1], head[M], nex[M << 1], cnt;
int belong[M], cha[M][251], res[M + B2 + 1], f[B1][B1][B1];
inline void add_edge(int u, int v) {
to[++ cnt] = v;
nex[cnt] = head[u];
head[u] = cnt;
}
void dfs(int u, int fu) {
ld[u] = ++ tim;
deep[ld[u]] = deep[ld[fu]] + 1;
maxdeep = max(maxdeep, deep[ld[u]]);
for(int i = head[u]; i; i = nex[i])
if(to[i] != fu)
dfs(to[i], u);
rd[u] = tim;
}
signed main() {
n = read();
q = read();
belong[1] = 1;
for(int i = 2; i <= n; ++ i) {
int u = read();
add_edge(u, i);
add_edge(i, u);
belong[i] = (i - 1) / B2 + 1;
}
dfs(1, 0);
for(int i = 1; i <= q; ++ i) {
int opt = read(), v = read(), l = ld[v], r = rd[v];
if(opt == 1) {
int x = read(), y = read(), z = read();
y = (deep[l] + y) % x;
if(x <= B1) {
if(belong[l] == belong[r]) {
for(int j = l; j <= r; ++ j)
if(deep[j] % x == y)
res[j] += z;
}
else {
for(int j = l; j <= belong[l] * B2; ++ j)
if(deep[j] % x == y)
res[j] += z;
for(int j = B2 * (belong[r] - 1) + 1; j <= r; ++ j)
if(deep[j] % x == y)
res[j] += z;
for(int j = belong[l] + 1; j < belong[r]; ++ j)
f[j][x][y] += z;
}
}
else {
if(belong[l] == belong[r]) {
for(int j = l; j <= r; ++ j)
if(deep[j] % x == y)
res[j] += z;
}
else {
for(int j = l; j <= belong[l] * B2; ++ j)
if(deep[j] % x == y)
res[j] += z;
for(int j = B2 * (belong[r] - 1) + 1; j <= r; ++ j)
if(deep[j] % x == y)
res[j] += z;
for(int j = y; j <= maxdeep; j += x)
cha[j][belong[l] + 1] += z, cha[j][belong[r]] -= z;
}
}
}
else {
int ans = res[l];
for(int j = 1; j <= belong[l]; ++ j)
ans += cha[deep[l]][j];
for(int j = 1; j <= B1; ++ j)
ans += f[belong[l]][j][deep[l] % j];
write(ans), putchar('\n');
}
}
}