【树链剖分差分】bzoj3626: [LNOI2014]LCA

把LCA深度转化的那一步还是挺妙的。之后就是差分加大力数据结构了。

Description

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。
（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）

Input

第一行2个整数n q。
接下来n-1行，分别表示点1到点n-1的父节点编号。
接下来q行，每行3个整数l r z。

Output

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

Sample Input

5 2
0
0
1
1
1 4 3
1 4 2

Sample Output

8
5

HINT

共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。

题目分析

我的做法&图片分析

由于树的标号是随便标的，所以这里的$[l,r]$区间操作在树上并没有什么大的特殊意义。

注意到如果$z$是给定的话，那么由于答案可减，我们可以对于序列来分块。

当然分块只是一种想法，再来挖掘一下$z$给定情况的性质。

这里求4和7的LCA。自然，LCA就是两点到根节点的第一个公共节点。不过这幅图可能还没看出什么。

这幅图里7号节点是z，4,6,8节点是与z节点查询的节点。我们把与z节点查询的节点都沿路径向根方向+1。

这样只需要查询z节点到根节点的路径权值和就能算出所有LCA的深度之和了。

注意到这样处理之后，预处理的信息对于任意的z都适用了。

至于题目要求的“根节点深度为1”，正好可以让我们把边权化为点权，做起来也更加方便。

更理论化的题解

在黄学长博客上看到一篇更加严谨的题解：

显然，暴力求解的复杂度是无法承受的。
考虑这样的一种暴力，我们把 z 到根上的点全部打标记，对于 l 到 r 之间的点，向上搜索到第一个有标记的点求出它的深度统计答案。观察到，深度其实就是上面有几个已标记了的点（包括自身）。所以，我们不妨把 z 到根的路径上的点全部 +1，对于 l 到 r 之间的点询问他们到根路径上的点权和。仔细观察上面的暴力不难发现，实际上这个操作具有叠加性，且可逆。也就是说我们可以对于 l 到 r 之间的点 i，将 i 到根的路径上的点全部 +1, 转而询问 z 到根的路径上的点（包括自身）的权值和就是这个询问的答案。把询问差分下，也就是用 [1, r] − [1, l − 1] 来计算答案，那么现在我们就有一个明显的解法。从 0 到 n − 1 依次插入点 i，即将 i 到根的路径上的点全部+1。离线询问答案即可。我们现在需要一个数据结构来维护路径加和路径求和，显然树链剖分或LCT 均可以完成这个任务。树链剖分的复杂度为 O((n + q)· log n · log n)，LCT的复杂度为 O((n + q)· log n)，均可以完成任务。至此，题目已经被我们完美解决。

（大力数据结构~）

  1 #include<bits/stdc++.h>
  2 const int MO = 201314;
  3 const int maxn = 50035;
  4 const int maxm = 50035;
  5 
  6 struct node
  7 {
  8     int fa,top,son,tot;
  9 }a[maxn];
 10 struct QRs
 11 {
 12     int x,id,opt;
 13     QRs(int a=0, int b=0, int c=0):x(a),id(b),opt(c) {}
 14     bool operator < (QRs a) const
 15     {
 16         return x < a.x;
 17     }
 18 }q[maxn<<1];
 19 int chain[maxn],chTot;
 20 int f[maxn<<2],add[maxn<<2];
 21 int edges[maxm],nxt[maxm],head[maxn],edgeTot;
 22 int ansAdd[maxn],ansDel[maxn],qr[maxn];
 23 int n,m,tot;
 24 
 25 int read()
 26 {
 27     char ch = getchar();
 28     int num = 0;
 29     bool fl = 0;
 30     for (; !isdigit(ch); ch = getchar())
 31         if (ch=='-') fl = 1;
 32     for (; isdigit(ch); ch = getchar())
 33         num = (num<<1)+(num<<3)+ch-48;
 34     if (fl) num = -num;
 35     return num;
 36 }
 37 void addedge(int u, int v)
 38 {
 39     edges[++edgeTot] = v, nxt[edgeTot] = head[u], head[u] = edgeTot;
 40 }
 41 void dfs1(int x, int fa)
 42 {
 43     a[x].fa = fa, a[x].son = -1, a[x].tot = 1;
 44     for (int i=head[x]; i!=-1; i=nxt[i])
 45     {
 46         int v = edges[i];
 47         dfs1(v, x), a[x].tot += a[v].tot;
 48         if (a[x].son==-1||a[a[x].son].tot < a[v].tot)
 49             a[x].son = v;
 50     }
 51 }
 52 void dfs2(int x, int top)
 53 {
 54     chain[x] = ++chTot, a[x].top = top;
 55     if (a[x].son==-1) return;
 56     dfs2(a[x].son, top);
 57     for (int i=head[x]; i!=-1; i=nxt[i])
 58         if (edges[i]!=a[x].son)
 59             dfs2(edges[i], edges[i]);
 60 }
 61 void pushup(int x)
 62 {
 63     f[x] = (f[x<<1]+f[x<<1|1])%MO;
 64 }
 65 void pushdown(int x, int l, int r)
 66 {
 67     if (add[x]){
 68         add[x<<1] += add[x], add[x<<1|1] += add[x];
 69         f[x<<1] += l*add[x], f[x<<1|1] += r*add[x];
 70         f[x<<1] %= MO, f[x<<1|1] %= MO;
 71         add[x] = 0;
 72     }
 73 }
 74 void update(int rt, int L, int R, int l, int r)
 75 {
 76     if (L <= l&&r <= R){
 77         add[rt]++, f[rt] = (f[rt]+r-l+1)%MO;
 78         return;
 79     }
 80     int mid = (l+r)>>1;
 81     pushdown(rt, mid-l+1, r-mid);
 82     if (L <= mid) update(rt<<1, L, R, l, mid);
 83     if (R > mid) update(rt<<1|1, L, R, mid+1, r);
 84     pushup(rt);
 85 }
 86 void updateChain(int x, int y)
 87 {
 88     while (a[x].top!=a[y].top)
 89     {
 90         update(1, chain[a[x].top], chain[x], 1, n);
 91         x = a[a[x].top].fa;
 92     }
 93     update(1, chain[y], chain[x], 1, n);
 94 }
 95 int query(int rt, int L, int R, int l, int r)
 96 {
 97     if (L <= l&&r <= R) return f[rt];
 98     int mid = (l+r)>>1, ret = 0;
 99     pushdown(rt, mid-l+1, r-mid);
100     if (L <= mid) ret += query(rt<<1, L, R, l, mid);
101     if (R > mid) ret += query(rt<<1|1, L, R, mid+1, r);
102     return ret%MO;
103 }
104 int queryChain(int x, int y)
105 {
106     int ret = 0;
107     while (a[x].top!=a[y].top)
108     {
109         ret += query(1, chain[a[x].top], chain[x], 1, n);
110         x = a[a[x].top].fa;
111     }
112     ret += query(1, chain[y], chain[x], 1, n);
113     return ret%MO;
114 }
115 int main()
116 {
117     memset(head, -1, sizeof head);
118     n = read(), m = read();
119     for (int i=1; i<n; i++) addedge(read(), i);
120     for (int i=1; i<=m; i++)
121     {
122         q[++tot] = QRs(read()-1, i, 0), q[++tot] = QRs(read(), i, 1);
123         qr[i] = read();
124     }
125     std::sort(q+1, q+tot+1);
126     dfs1(0, -1);
127     dfs2(0, 0);
128     int now = -1;
129     for (int i=1; i<=tot; i++)
130     {
131         while (now < q[i].x)
132             updateChain(++now, 0);
133         int id = q[i].id;
134         if (q[i].opt)
135             ansAdd[id] = queryChain(qr[id], 0);
136         else ansDel[id] = queryChain(qr[id], 0);
137     }
138     for (int i=1; i<=m; i++)
139         printf("%d
",(ansAdd[i]-ansDel[i]+MO)%MO);
140     return 0;
141 }

END