_rqy's Blog

一只猫猫,想成为天才少女数学家!

0%

BZOJ3626 [LNOI2014] LCA

Description

nn个点的树,qq个询问,每个询问给出l,r,xl,r,x,求i=lrdeplca(i,x)\sum_{i=l}^r dep_{lca(i, x)}。根的深度是11n,q50000n, q\leqslant 50000

Solution

树剖?啥?能吃吗?

分块大法好!

将节点(按编号)每SS个分一块,预处理出fi,j=xblockideplca(x,j)f_{i,j}=\sum_{x\in block_i}dep_{lca(x,j)},可以每个块dfs一遍。

然后对jj这一维搞一个前缀和;再dfs一遍求dfs序(那种用来RMQ求LCA的),预处理ST表以O(1)O(1)LCA。

然后查询时整块直接前缀和相减;块内O(S)O(S)查询。

总时间复杂度O(n2S+qS)O(\frac{n^2}S+qS)SSnq\frac n{\sqrt q}时最小,为O(nq)O(n\sqrt q)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
}