[树链剖分][差分] Luogu P4211 LCA

题目描述

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。有q次询问，每次询问给出l r z，求 $sum_{l leq i leq r}dep[LCA(i,z)]∑l≤i≤rdep[LCA(i,z)]$

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

8
5

说明

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

题解

我们把每要询问的点往上都打上标记，然后把z点往上找到每个标记第一次出现的位置
其实我们可以发现，每个标记的深度等同于它上面有多少个和它一样的标记
那么我们可以把每个点到根的路径都+1，然后询问z到根的和，就是答案了
可以用树链剖分搞
区间[l,r]的答案=区间[1,r]的答案-区间[1,l-1]的答案，那么我们把每个询问拆成两个，一个+，一个-

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N 50010
 6 using namespace std;
 7 const int mo=201314;
 8 struct node{int p,z,id,bz;}Q[N*2];
 9 struct edge{int to,from;}e[N]; 
10 int n,m,cnt,tot,p,t[N*3],tag[N*3],ans[N*2],head[N],size[N],son[N],w[N],top[N],fa[N];
11 bool cmp(node x,node y) {return x.p<y.p;}
12 void insert(int x,int y) { e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt; }
13 void dfs(int x)
14 {
15     size[x]=1;
16     for (int i=head[x];i;i=e[i].from)
17     {
18         dfs(e[i].to),size[x]+=size[e[i].to];
19         if (size[e[i].to]>size[son[x]]) son[x]=e[i].to;
20     }
21 }
22 void dfs1(int x,int y)
23 {
24     w[x]=++tot,top[x]=y;
25     if (!son[x]) return;
26     dfs1(son[x],y);
27     for (int i=head[x];i;i=e[i].from) if (e[i].to!=son[x]) dfs1(e[i].to,e[i].to); 
28 }
29 void out(int d,int x,int len) { (t[d]+=len*x)%=mo,tag[d]+=x; }
30 void pushdown(int d,int l,int r) 
31 {
32     if (tag[d]) 
33     {
34         int mid=l+r>>1;
35         out(d*2,tag[d],mid-l+1),out(d*2+1,tag[d],r-mid),tag[d]=0;
36     }
37 } 
38 void change(int d,int l,int r,int x,int y)
39 {
40     if (l==x&&r==y) { out(d,1,r-l+1); return; }
41     int mid=l+r>>1; pushdown(d,l,r);
42     if (y<=mid) change(d*2,l,mid,x,y);
43     else if (x>mid) change(d*2+1,mid+1,r,x,y);
44     else change(d*2,l,mid,x,mid),change(d*2+1,mid+1,r,mid+1,y);
45     t[d]=(t[d*2]+t[d*2+1])%mo;
46 }
47 int find(int d,int l,int r,int x,int y) 
48 {
49     if (l==x&&r==y) return t[d];
50     int mid=l+r>>1; pushdown(d,l,r);
51     if (y<=mid) return find(d*2,l,mid,x,y);
52     else if (x>mid) return find(d*2+1,mid+1,r,x,y);
53     else return find(d*2,l,mid,x,mid)+find(d*2+1,mid+1,r,mid+1,y);
54 }
55 void work(int x)
56 {
57     int f=top[x];
58     while (x) change(1,1,n,w[f],w[x]),x=fa[f],f=top[x];
59 }
60 int query(int x)
61 {
62     int f=top[x],ans=0;
63     while (x) (ans+=find(1,1,n,w[f],w[x]))%=mo,x=fa[f],f=top[x];
64     return ans;
65 }
66 int main()
67 {
68     scanf("%d%d",&n,&m);
69     for (int i=2;i<=n;i++) scanf("%d",&fa[i]),insert(++fa[i],i);
70     dfs(1),dfs1(1,1),tot=0;
71     for (int i=1,l,r;i<=m;i++) scanf("%d%d%d",&l,&r,&Q[++tot].z),l++,r++,Q[tot].z++,Q[tot].p=l-1,Q[tot].id=i,Q[tot].bz=-1,Q[++tot].p=r,Q[tot].id=i,Q[tot].bz=1,Q[tot].z=Q[tot-1].z;
72     sort(Q+1,Q+tot+1,cmp); while (!Q[p+1].p) p++;
73     for (int i=1;i<=n;i++) 
74     {
75         work(i);
76         while (Q[p+1].p==i) p++,ans[Q[p].id]+=query(Q[p].z)*Q[p].bz;    
77     } 
78     for (int i=1;i<=m;i++) printf("%d
",(ans[i]+mo)%mo);
79 }