BZOJ3626 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。

Source

数据已加强 by saffah

正解：树链剖分+线段树

解题报告：

　　我这种蒟蒻一看到题目第一反应就是打暴力，真是没戏了。

　　想了20分钟没想出来就弃疗了，直接看了hzwer神犇的题解，%%%hzwer：http://hzwer.com/3891.html

　　其实我只看了一眼那个结论我马上就会打了，瞬间变水题。关键是操作具有很多奇奇怪怪的性质，而且转化成求路径上的点权和。

　　正版推导：

　　考虑这样的一种暴力，我们把 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 //It is made by jump~
  2 #include <iostream>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <cstdio>
  6 #include <cmath>
  7 #include <algorithm>
  8 #include <ctime>
  9 #include <vector>
 10 #include <queue>
 11 #include <map>
 12 #include <set>
 13 using namespace std;
 14 typedef long long LL;
 15 const int MAXN = 50011;
 16 const int MOD = 201314;
 17 const int MAXQ = 100011;
 18 int n,q,ecnt;
 19 int first[MAXN],next[MAXN*2],to[MAXN*2];
 20 int father[MAXN],top[MAXN],son[MAXN],size[MAXN],deep[MAXN],id[MAXN],pre[MAXN];
 21 int ql,qr,daan;
 22 
 23 struct wen{
 24     int pos,z,id,ans;
 25 }a[MAXQ];
 26 
 27 struct node{
 28     int sum,lazy,l,r,size;
 29 }jump[MAXN*4];
 30 
 31 inline int getint()
 32 {
 33     int w=0,q=0;
 34     char c=getchar();
 35     while((c<'0' || c>'9') && c!='-') c=getchar();
 36     if (c=='-')  q=1, c=getchar();
 37     while (c>='0' && c<='9') w=w*10+c-'0', c=getchar();
 38     return q ? -w : w;
 39 }
 40  
 41 inline void dfs(int x,int fa){
 42     size[x]=1;
 43     for(int i=first[x];i;i=next[i]) {
 44     int v=to[i]; deep[v]=deep[x]+1;
 45     dfs(v,x);
 46     size[x]+=size[v];
 47     if(size[v]>size[son[x]]) son[x]=v;
 48     }
 49 }
 50 
 51 inline void dfs2(int x,int fa){
 52     id[x]=++ecnt; pre[ecnt]=x;
 53     if(son[x]) top[son[x]]=top[x],dfs2(son[x],x);
 54     for(int i=first[x];i;i=next[i]) {
 55     int v=to[i];
 56     if(v!=son[x]) {
 57         top[v]=v;
 58         dfs2(v,x);
 59     }
 60     }
 61 }
 62 
 63 inline bool cmp(wen q,wen qq){ return q.pos<qq.pos; }
 64 inline bool ccmp(wen q,wen qq){ return q.id<qq.id; }
 65 
 66 inline void pushdown(int x){
 67     if(jump[x].size==1) return ;
 68     if(jump[x].lazy) {
 69     int lc=x*2,rc=lc+1;
 70     jump[lc].lazy+=jump[x].lazy;jump[rc].lazy+=jump[x].lazy;
 71     jump[lc].sum+=jump[x].lazy*jump[lc].size;jump[rc].sum+=jump[x].lazy*jump[rc].size;
 72     jump[x].lazy=0;    
 73     }
 74 }
 75 
 76 inline void update(int root,int l,int r){
 77     pushdown(root);
 78     if(ql<=l && r<=qr) {
 79     jump[root].lazy++;
 80     jump[root].sum+=jump[root].size;
 81     return ;
 82     }
 83     int mid=(l+r)/2; int lc=root*2,rc=lc+1;
 84     if(ql<=mid) update(lc,l,mid); if(qr>mid) update(rc,mid+1,r); 
 85     jump[root].sum=jump[lc].sum+jump[rc].sum;
 86 }
 87 
 88 inline void query(int root,int l,int r){
 89     pushdown(root);
 90     if(ql<=l && r<=qr) {    
 91     daan+=jump[root].sum;
 92     if(daan>=MOD) daan=daan%MOD;
 93     return ;
 94     }
 95     int mid=(l+r)/2; int lc=root*2,rc=lc+1;    
 96     if(ql<=mid) query(lc,l,mid); if(qr>mid) query(rc,mid+1,r);
 97     jump[root].sum=jump[lc].sum+jump[rc].sum;
 98 }
 99 
100 inline void lca(int x){
101     int f1=top[x];
102     while(x) {
103     ql=id[f1],qr=id[x];
104     update(1,1,n);
105     x=father[f1]; f1=top[x];
106     }
107 }
108 
109 inline int up(int x){
110     int f1=top[x];
111     int total=0;
112     while(x) {
113     ql=id[f1]; qr=id[x]; daan=0;
114     query(1,1,n);
115     total+=daan;
116     x=father[f1]; f1=top[x];
117     if(total>=MOD) total%=MOD;
118     }
119     return total;
120  }
121 
122 inline void build(int root,int l,int r){
123     jump[root].l=l; jump[root].r=r; jump[root].size=r-l+1;
124     if(l==r) return ;    
125     int mid=(l+r)/2; int lc=root*2,rc=lc+1; 
126     build(lc,l,mid); build(rc,mid+1,r);
127 }
128 
129 inline void work(){
130     n=getint(); q=getint();   
131     for(int i=1;i<n;i++) {
132     father[i+1]=getint()+1;    
133     next[++ecnt]=first[father[i+1]]; to[ecnt]=i+1; first[father[i+1]]=ecnt;
134     }
135     deep[1]=1; dfs(1,0); top[1]=1; ecnt=0; dfs2(1,0);
136     int x,y,z;
137     ecnt=0;
138     for(int i=1;i<=q;i++) {
139     x=getint()+1; y=getint()+1; z=getint()+1;
140     a[++ecnt].pos=x-1; a[ecnt].id=ecnt; a[ecnt].z=z;
141     a[++ecnt].pos=y; a[ecnt].id=ecnt; a[ecnt].z=z;
142     }
143     sort(a+1,a+ecnt+1,cmp);
144     int now=0;
145     build(1,1,n);
146     for(int i=1;i<=ecnt;i++) {
147     while(now<a[i].pos) {
148         lca(now+1);  now++;
149     }
150     a[i].ans=up(a[i].z);    if(a[i].ans>MOD) a[i].ans%=MOD;
151     }
152 
153     sort(a+1,a+ecnt+1,ccmp);
154     for(int i=1;i<=ecnt;i+=2) printf("%d
",( (a[i+1].ans-a[i].ans)+MOD )%MOD);
155 }
156  
157 int main()
158 {
159     work();
160     return 0;
161 }