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

【BZOJ3626】LCA(LNOI2014)-树链剖分+离线处理

程序员文章站 2022-05-27 14:41:30
...

测试地址:LCA
做法:本题需要用到树链剖分+离线处理。
题目中要求的式子看上去非常难求,怎么办呢?
我们考虑求z的每个祖先对答案的贡献。令zi级祖先为fa(z,i)siz(v,l,r)为以v点为根的子树中有多少个编号在[l,r]中的点,那么式子可以转化成:
i=0dep(z)1dep(fa(z,i))(siz(fa(z,i),l,r)siz(fa(z,i1),l,r))
因为dep(fa(z,i))=dep(fa(z,i1))1,所以上式可以转化为:
i=0dep(z)1siz(fa(z,i),l,r)
我们发现,如果我们对每个点v维护siz(v,l,r),我们就可以通过树链剖分来统计答案。然而我们发现这个不太好维护,但把它改成维护siz(v,0,r)siz(v,0,l1)的前缀和形式就明朗多了,对于一个点v,插入后会对它的所有祖先的siz做出1的贡献,这个显然能用树链剖分维护,因此我们离线处理所有询问,按编号从小到大插入点,然后对影响到的询问做出修改即可,时间复杂度为O(nlog2n)
我傻逼的地方:一开始居然没有看到对201314取模……太傻逼了……
以下是本人代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,first[50010]={0},tot=0,tim=0;
ll ans[50010]={0},seg[200010]={0},p[200010]={0};
int fa[50010],siz[50010],son[50010],top[50010],pos[50010];
struct edge
{
    int v,next;
}e[50010];
struct query
{
    int id,type;
    int pos,z;
}q[100010];

bool cmp(query a,query b)
{
    return a.pos<b.pos;
}

void insert(int a,int b)
{
    e[++tot].v=b;
    e[tot].next=first[a];
    first[a]=tot;
}

void dfs1(int v)
{
    son[v]=-1;
    siz[v]=1;
    for(int i=first[v];i;i=e[i].next)
    {
        dfs1(e[i].v);
        if (son[v]==-1||siz[e[i].v]>siz[son[v]])
            son[v]=e[i].v;
        siz[v]+=siz[e[i].v];
    }
}

void dfs2(int v,int tp)
{
    top[v]=tp;
    pos[v]=++tim;
    if (son[v]!=-1) dfs2(son[v],tp);
    for(int i=first[v];i;i=e[i].next)
        if (e[i].v!=son[v]) dfs2(e[i].v,e[i].v);
}

void pushdown(int no,int l,int r)
{
    if (p[no])
    {
        int mid=(l+r)>>1;
        p[no<<1]+=p[no],p[no<<1|1]+=p[no];
        seg[no<<1]+=(ll)(mid-l+1)*p[no];
        seg[no<<1|1]+=(ll)(r-mid)*p[no];
        p[no]=0;
    }
}

void pushup(int no)
{
    seg[no]=seg[no<<1]+seg[no<<1|1];
}

void segmodify(int no,int l,int r,int s,int t)
{
    if (l>=s&&r<=t)
    {
        seg[no]+=(ll)(r-l+1);
        p[no]++;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(no,l,r);
    if (s<=mid) segmodify(no<<1,l,mid,s,t);
    if (t>mid) segmodify(no<<1|1,mid+1,r,s,t);
    pushup(no);
}

ll segquery(int no,int l,int r,int s,int t)
{
    if (l>=s&&r<=t) return seg[no];
    int mid=(l+r)>>1;
    ll sum=0;
    pushdown(no,l,r);
    if (s<=mid) sum+=segquery(no<<1,l,mid,s,t);
    if (t>mid) sum+=segquery(no<<1|1,mid+1,r,s,t);
    return sum;
}

void modify(int x)
{
    while(x!=-1)
    {
        segmodify(1,1,n,pos[top[x]],pos[x]);
        x=fa[top[x]];
    }
}

ll query(int x)
{
    ll sum=0;
    while(x!=-1)
    {
        sum+=segquery(1,1,n,pos[top[x]],pos[x]);
        x=fa[top[x]];
    }
    return sum;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        insert(x,i);
        fa[i]=x;
    }
    fa[0]=-1;
    dfs1(0);
    dfs2(0,0);

    tot=0;
    for(int i=1;i<=m;i++)
    {
        int l,r,z;
        scanf("%d%d%d",&l,&r,&z);
        q[++tot].id=i,q[tot].type=0,q[tot].pos=l-1,q[tot].z=z;
        q[++tot].id=i,q[tot].type=1,q[tot].pos=r,q[tot].z=z;
    }
    sort(q+1,q+tot+1,cmp);

    int last=1;
    while(q[last].pos==-1) last++;
    for(int i=0;i<n;i++)
    {
        modify(i);
        while(last<=tot&&q[last].pos==i)
        {
            if (q[last].type) ans[q[last].id]+=query(q[last].z);
            else ans[q[last].id]-=query(q[last].z);
            last++;
        }
    }

    for(int i=1;i<=m;i++)
        printf("%lld\n",ans[i]%201314);

    return 0;
}