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

深碍√TFBOYSˉ_ 2021-11-02 10:22 277阅读 0赞

## 题目描述 ##

给出一个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：

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

输出样例\#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\n",(ans[i]+mo)%mo);
    79 }

转载于:https://www.cnblogs.com/Comfortable/p/11212238.html