欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

bzoj3626: [LNOI2014]LCA(离线处理+树链剖分)

程序员文章站 2022-05-27 14:38:06
...

题目传送门

解法:
对于任意一个询问:
l r z
对于任意一个点来说。他对答案的贡献实际上是LCA(i,z)的深度。
也就是lca到根的点数。
那么我们可以每个点到根的路径都加1。然后询问下z到根的路径上的答案总和其实就是答案啊。
显然可以分成两个区间,一个1到l-1,一个1到r。l到r的答案用两个答案相减,正确性显然。

那么离线处理。
把每个操作都分成两个区间。
然后分别按照右端点排序。把每个点到路径的点都加1。
然后在询问z到根答案即可。
过程用树链剖分实现即可。

代码实现:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
struct node {int x,y,next;}a[110000];int len,last[110000];const int mod=201314;
void ins(int x,int y) {len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
int tot[110000],son[110000],fa[110000];
void pre_tree_node(int x) {
    son[x]=0;tot[x]=1;
    for(int k=last[x];k;k=a[k].next) {
        int y=a[k].y;pre_tree_node(y);tot[x]+=tot[y];if(tot[y]>tot[son[x]])son[x]=y;
    }
}
int z,ys[110000],top[110000];
void pre_tree_edge(int x,int tp) {
    ys[x]=++z;top[x]=tp;
    if(son[x]!=0)pre_tree_edge(son[x],tp);
    for(int k=last[x];k;k=a[k].next) {
        int y=a[k].y;
        if(y!=son[x])pre_tree_edge(y,y);
    }
}
struct trnode {int l,r,lc,rc,c,lazy,s;}tr[210000];int trlen;
void bt(int l,int r) {
    int now=++trlen;
    tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;tr[now].c=0;tr[now].lazy=0;tr[now].s=r-l+1;
    if(l<r) {int mid=(l+r)/2;tr[now].lc=trlen+1;bt(l,mid);tr[now].rc=trlen+1;bt(mid+1,r);}
}
void update(int now) {
    int lc=tr[now].lc,rc=tr[now].rc;
    if(lc==-1)return ;
    tr[lc].c+=tr[lc].s*tr[now].lazy;tr[rc].c+=tr[rc].s*tr[now].lazy;
    tr[lc].lazy+=tr[now].lazy;tr[rc].lazy+=tr[now].lazy;tr[now].lazy=0;
}
void change(int now,int l,int r) {
    if(tr[now].lazy!=0)update(now);
    if(tr[now].l==l&&tr[now].r==r) {tr[now].c=tr[now].c+tr[now].s;tr[now].lazy++;return ;}
    int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
    if(r<=mid)change(lc,l,r);else if(l>mid)change(rc,l,r);
    else {change(lc,l,mid);change(rc,mid+1,r);}
    tr[now].c=tr[lc].c+tr[rc].c;
}
int find_sum(int now,int l,int r) {
    if(tr[now].lazy!=0)update(now);
    if(tr[now].l==l&&tr[now].r==r)return tr[now].c;
    int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
    if(r<=mid)return find_sum(lc,l,r);else if(l>mid)return find_sum(rc,l,r);
    else return find_sum(lc,l,mid)+find_sum(rc,mid+1,r);
}
void solve_change(int x) {
    int tx=top[x];
    while(tx!=1) {change(1,ys[tx],ys[x]);x=fa[tx];tx=top[x];}
    change(1,ys[tx],ys[x]);return ;
}
int solve_sum(int x) {
    int tx=top[x],ans=0;
    while(tx!=1) {ans+=find_sum(1,ys[tx],ys[x]);ans%=mod;x=fa[tx];tx=top[x];}
    ans+=find_sum(1,ys[tx],ys[x]);ans%=mod;return ans;
}
struct Q {int ed,s,t,z;}e[110000];
bool cmp(Q n1,Q n2) {return n1.ed<n2.ed;}
int ans2[110000],ans1[110000];
int main() {
    int n,m;scanf("%d%d",&n,&m);len=0;memset(last,0,sizeof(last));
    for(int i=2;i<=n;i++) {int x;scanf("%d",&x);x++;ins(x,i);fa[i]=x;}
    pre_tree_node(1);z=0;pre_tree_edge(1,1);trlen=0;bt(1,z);int sum=0;
    for(int i=1;i<=m;i++) {
        int l,r,Z;scanf("%d%d%d",&l,&r,&Z);l++;r++;Z++;
        sum++;e[sum].s=i;e[sum].ed=l-1;e[sum].z=Z;e[sum].t=-1;
        sum++;e[sum].s=i;e[sum].ed=r;e[sum].z=Z;e[sum].t=1;
    }sort(e+1,e+1+sum,cmp);
    int now=0;
    for(int i=1;i<=sum;i++) {
        while(now<e[i].ed) {now++;solve_change(now);}
        if(e[i].t==1) ans1[e[i].s]=solve_sum(e[i].z);
        else ans2[e[i].s]=solve_sum(e[i].z);
    }for(int i=1;i<=m;i++)printf("%d\n",(ans1[i]-ans2[i]+mod)%mod);
    return 0;
}