BZOJ3626 [LNOI2014] LCA

发表于 更新于 分类于 阅读次数：

Description

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

Solution

树剖？啥？能吃吗？

分块大法好！

将节点（按编号）每SS个分一块，预处理出fi,j=∑x∈blockideplca(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)，SS取nq\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;
}