BZOJ3626 [LNOI2014] LCA
2018 年 03 月 14 日发布.
Description
$n$个点的树，$q$个询问，每个询问给出$l,r,x$，求$\sum_{i=l}^r dep_{lca(i, x)}$。根的深度是$1$。$n, q\leqslant 50000$。
Solution
树剖？啥？能吃吗？
分块大法好！
将节点（按编号）每$S$个分一块，预处理出$f_{i,j}=\sum_{x\in block_i}dep_{lca(x,j)}$，可以每个块dfs一遍。
然后对$j$这一维搞一个前缀和；再dfs一遍求dfs序（那种用来RMQ求LCA的），预处理ST表以$O(1)$LCA。
然后查询时整块直接前缀和相减；块内$O(S)$查询。
总时间复杂度$O(\frac{n^2}S+qS)$，$S$取$\frac n{\sqrt q}$时最小，为$O(n\sqrt q)$。
Code
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
const int N = 50050;
const int B = 300;
const int mod = 201314;
int ls[N], rb[N], pos[N], minv[20][N * 2], min2[N * 2];
int fa[N], n, cnt = 0;
void dfs0(int x, int d) {
minv[0][pos[x] = cnt++] = d;
for (int i = ls[x]; i; i = rb[i]) {
dfs0(i, d + 1);
if (rb[i]) minv[0][cnt++] = d;
}
}
void work() {
for (int i = 0, k = 1; k < cnt; ++i, k <<= 1) {
for (int j = 0; j + k <= cnt; ++j)
minv[i + 1][j] = std::min(minv[i][j], minv[i][j + k]);
for (int j = k; j < (k << 1); ++j) min2[j] = i;
}
}
int d(int x, int y) {
x = pos[x]; y = pos[y];
if (x > y) std::swap(x, y);
int k = min2[y - x + 1];
return std::min(minv[k][x], minv[k][y - (1 << k) + 1]);
}
int siz[N];
int dfs1(int x, int b) {
siz[x] = (x / B == b);
for (int i = ls[x]; i; i = rb[i]) siz[x] += dfs1(i, b);
return siz[x];
}
int ans[N / B + 2][N];
void dfs2(int x, int b, int v) {
ans[b][x] = ((v += siz[x]) %= mod) + (b ? ans[b - 1][x] : 0);
if (ans[b][x] > mod) ans[b][x] -= mod;
for (int i = ls[x]; i; i = rb[i]) dfs2(i, b, v);
}
int main() {
int q;
scanf("%d%d", &n, &q);
memset(fa, -1, sizeof fa);
for (int i = 1; i < n; ++i) {
scanf("%d", &fa[i]);
rb[i] = ls[fa[i]]; ls[fa[i]] = i;
}
dfs0(0, 1);
work();
for (int b = 0; b * B < n; ++b) { dfs1(0, b); dfs2(0, b, 0); }
for (int l, r, x; q; --q) {
scanf("%d%d%d", &l, &r, &x);
int lb = (l + B - 1) / B, rb = r / B;
long long ansv = 0;
if (lb <= rb) {
ansv = (ans[rb - 1][x] - (lb ? ans[lb - 1][x] : 0) + mod) % mod;
for (int i = l; i < lb * B; ++i) ansv += d(i, x);
for (int i = rb * B; i <= r; ++i) ansv += d(i, x);
} else
for (int i = l; i <= r; ++i) ansv += d(i, x);
printf("%d\n", (int)(ansv % mod));
}
return 0;
}