bzoj3626 [LNOI2014]LCA

[LNOI2014]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。

暴力可以拿0分，o(￣ヘ￣o#)

这个其实也是十分简单的，离线求差分，之类的操作，用树链剖分维护。

Orz这题真的太鬼了，除了暴力求LCA再暴力求根本想不到该怎么做，小伙子啊，迟早要完！！！

看了题解之后膝盖又一次跪烂了。。。

于是接下来就一步一步还原大佬们是怎么YY出来的吧

新暴力雏形：

对于每个z,我们把z到根节点上的所有点都打上标记，然后对于区间[l,r]的点就不断向上跳爸爸，直到跳到一个打了标记的点，把这个点的深度加上。。。

也就是说只有这些被z跳到的点的深度才是有贡献的。。。

考虑到深度的定义。。。

于是有了并没有一点改进的暴力：

把z到根的路径上的点权加1，l--r中的每个点的贡献相当于查询该点到根节点的路径上的权值和(这个值也就等价于第一种暴力中找到的第一个有标记的点的深度。。。)

这样手动模拟或脑子YY是显然没有问题的。。。

我们发现这种操作是有可逆性的，重复性的(深度叠加)。。。

那么上面的第二种暴力的做法等价于如下做法：

把l--r间的每个点到根节点路径上的点权加1，然后对于每个z，其答案就是z到根的权值和。。。

于是就变成了下面这样：

于是我们可以想到一个比较明显的做法了。。。依次加入0--n-1的点并把该点到根的路径上的点权加1；

我们考虑用前缀和的思想，即用ans[r]-ans[l-1]。。。

我们对于每个询问的l和r拆成两个询问，把这些询问离线下来sort一遍，维护一个head指针一直加点。。。，head指针是单增的，

就不需要像CJK神犇那样对每个询问l和r还要打个莫队。。。

我们需要一个数据结构来维护区间修改和区间求和。。。于是我做死的打了一个LCT，相当于只要下放lazy和维护一个子树大小。。。

附上大佬题解

转自：http://www.cnblogs.com/qt666/p/6490006.html

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #define ll long long
  7 #define inf 1000000007
  8 #define mod 201314
  9 
 10 using namespace std;
 11 const int NN=50007;
 12 
 13 int n,m,place;
 14 int bin[20];
 15 int son[NN],fa[NN],belong[NN],pl[NN],deep[NN];
 16 int cnt=0,head[NN],next[NN*2],rea[NN*2];
 17 
 18 struct que{int z,ans1,ans2;}q[NN];
 19 struct data{int num,p;bool flag;}a[NN*2];
 20 struct seg{int l,r,sum,tag,size;}t[NN*4];
 21 
 22 bool cmp(data x,data y)
 23 {
 24     return x.p<y.p;
 25 }
 26 void add(int u,int v)
 27 {
 28     cnt++;
 29     next[cnt]=head[u];
 30     head[u]=cnt;
 31     rea[cnt]=v;    
 32 }
 33 void dfs1(int x)
 34 {
 35     son[x]=1;
 36     for(int i=head[x];i!=-1;i=next[i])
 37     {
 38         int v=rea[i];
 39         if(v==fa[x])continue;
 40         deep[v]=deep[x]+1;
 41         fa[v]=x;
 42         dfs1(v);
 43         son[x]+=son[v];
 44     }
 45 }
 46 void dfs2(int x,int chain)
 47 {
 48     belong[x]=chain;pl[x]=++place;
 49     int k=n;
 50     for(int i=head[x];i!=-1;i=next[i])
 51     {
 52         int v=rea[i];
 53         if(v!=fa[x]&&son[v]>son[k]) k=v;
 54     }
 55     if(k!=n) dfs2(k,chain);
 56     for(int i=head[x];i!=-1;i=next[i])
 57     {
 58         int v=rea[i];
 59         if(v!=fa[x]&&v!=k) dfs2(v,v);
 60     }
 61 }
 62 inline void pushdown(int k)
 63 {
 64     if(t[k].l==t[k].r||!t[k].tag)return;
 65     int tag=t[k].tag;t[k].tag=0;
 66     t[k<<1].sum=t[k<<1].sum+t[k<<1].size*tag;
 67     t[k<<1|1].sum=t[k<<1|1].sum+t[k<<1|1].size*tag;
 68     t[k<<1].tag=t[k<<1].tag+tag;
 69     t[k<<1|1].tag=t[k<<1|1].tag+tag;
 70 }
 71 void build(int k,int l,int r)
 72 {
 73     t[k].l=l;t[k].r=r;t[k].size=r-l+1;
 74     if(l==r)return;
 75     int mid=(l+r)>>1;
 76     build(k<<1,l,mid);
 77     build(k<<1|1,mid+1,r);
 78 }
 79 void update(int k,int x,int y)//tag标记加1而已 
 80 {
 81     pushdown(k);
 82     int l=t[k].l,r=t[k].r;
 83     if(l==x&&y==r)
 84     {
 85         t[k].tag++;t[k].sum+=t[k].size;
 86         return;
 87     }
 88     int mid=(l+r)>>1;
 89     if(y<=mid)update(k<<1,x,y);
 90     else if(x>mid)update(k<<1|1,x,y);
 91     else 
 92     {
 93         update(k<<1,x,mid);
 94         update(k<<1|1,mid+1,y);
 95     }
 96     t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
 97 }
 98 void solve_update(int x,int f)
 99 {
100     while(belong[x]!=belong[f])
101     {
102         update(1,pl[belong[x]],pl[x]);
103         x=fa[belong[x]];
104     }
105     update(1,pl[f],pl[x]);
106 }
107 int query(int k,int x,int y)
108 {
109     pushdown(k);
110     int l=t[k].l,r=t[k].r;
111     if(l==x&&y==r)return t[k].sum;
112     int mid=(l+r)>>1;
113     if(y<=mid)return query(k<<1,x,y);
114     else if(x>mid)return query(k<<1|1,x,y);
115     else return query(k<<1,x,mid)+query(k<<1|1,mid+1,y);
116 }
117 int solve_query(int x,int f)
118 {
119     int sum=0;
120     while(belong[x]!=belong[f])
121     {
122         sum+=query(1,pl[belong[x]],pl[x]);
123         sum%=mod;
124         x=fa[belong[x]];
125     }
126     sum+=query(1,pl[f],pl[x]);
127     sum%=mod;
128     return sum;
129 }
130 int main()
131 {
132     memset(head,-1,sizeof(head));
133     bin[0]=1;
134     for(int i=1;i<20;i++)
135         bin[i]=(bin[i-1]<<1);
136     scanf("%d%d",&n,&m);
137     for(int i=1;i<n;i++)
138     {
139         int x;
140         scanf("%d",&x);
141         add(x,i);
142     }
143     int tot=0;
144     for(int i=1;i<=m;i++)
145     {
146         int l,r;
147         scanf("%d%d%d",&l,&r,&q[i].z);
148         a[++tot].p=l-1;a[tot].num=i;a[tot].flag=0;
149         a[++tot].p=r;a[tot].num=i;a[tot].flag=1;
150     }
151     build(1,1,n);
152     sort(a+1,a+tot+1,cmp);
153     dfs1(0);dfs2(0,0);
154     int now=-1;
155     for(int i=1;i<=tot;i++)
156     {
157         while(now<a[i].p)
158         {
159             now++;
160             solve_update(now,0);
161         }
162         int t=a[i].num;
163         if(!a[i].flag)q[t].ans1=solve_query(q[t].z,0);
164         else q[t].ans2=solve_query(q[t].z,0);
165     }
166     for(int i=1;i<=m;i++)
167         printf("%d
",(q[i].ans2-q[i].ans1+mod)%mod);
168 }