[BZOJ3626][LNOI2014]LCA(树链剖分,线段树)

发布于 2018-01-20  76 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3626][LNOI2014]LCA(树链剖分,线段树)

Description

给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。有q次询问,每次询问给出l r z,求\(\sum_{l<=i<=r}dep[LCA(i,z)]\)。(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)

Http

BZOJ

Tag

树链剖分,离线

解决思路

先考虑单次询问,如果我们对于点\(i \in [l,r]\),都把\(i\)到根的路径加一,那么从我们询问的点到根的路径权值之和就是此次询问的答案。
处理路径覆盖,我们可以采用树链剖分+线段树的方式实现。
现在考虑多组数据,我们可以离线操作,把输入读进来排序,记录左端点和右端点分别处理,这样就可以回答多组询问了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=60010;
const int maxM=maxN*2;
const int Mod=201314;
const int inf=2147483647;

class Question//每一个询问
{
public:
    int pos,id;//位置,询问的编号
    int lr;//是id这个询问的左区间还是右区间
};

bool operator < (Question A,Question B)//排序区间方便离线
{
    return A.pos<B.pos;
}

int n;
int edgecnt=-1,Head[maxN],Next[maxM],V[maxM];//图
int Depth[maxN],Fa[maxN],Size[maxN],Hson[maxN],Top[maxN];//树链剖分
int idcnt=0,Id[maxN];
int Seg[maxN*8],Lazy[maxN*8];//线段树
Question Qn[maxN*4];//询问
int QPos[maxN],Ans[maxN];//答案

void Add_Edge(int u,int v);
void dfs1(int u);
void dfs2(int u,int nowtop);
void TCAdd(int pos);
int TCQuery(int pos);
void SegModify(int now,int l,int r,int ql,int qr,int delta);
int SegQuery(int now,int l,int r,int ql,int qr);
void PushDown(int now,int l,int r);
void SegOutp(int now,int l,int r);

int main()
{
    mem(Head,-1);int Q;
    scanf("%d%d",&n,&Q);
    for (int i=1;i<n;i++){ int fa;scanf("%d",&fa);Add_Edge(fa+1,i+1);Fa[i+1]=fa+1; }
    //树链剖分预处理
    Depth[1]=1;
    dfs1(1);
    dfs2(1,1);
    //读入询问
    int qtot=0;
    for (int i=1;i<=Q;i++)
    {
        int l,r;scanf("%d%d%d",&l,&r,&QPos[i]);l++;r++;QPos[i]++;
        if (l!=1) {Qn[++qtot].id=i;Qn[qtot].pos=l-1;Qn[qtot].lr=0;}//注意这里的-1
        Qn[++qtot].id=i;Qn[qtot].pos=r;Qn[qtot].lr=1;
    }
    sort(&Qn[1],&Qn[qtot+1]);//排序询问
    int nowr=0;
    for (int i=1;i<=qtot;i++)
    {
        while (nowr<Qn[i].pos)
        {
            nowr++;TCAdd(nowr);//插入
        }
        //得到询问
        if (Qn[i].lr==0) Ans[Qn[i].id]-=TCQuery(QPos[Qn[i].id]);
        else Ans[Qn[i].id]+=TCQuery(QPos[Qn[i].id]);
    }
    for (int i=1;i<=Q;i++)
        printf("%d\n",(Ans[i]%Mod+Mod)%Mod);
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

void dfs1(int u)
{
    Size[u]=1;
    int mxsz=0;
    for (int i=Head[u];i!=-1;i=Next[i])
    {
        Depth[V[i]]=Depth[u]+1;
        dfs1(V[i]);
        Size[u]+=Size[V[i]];
        if (Size[V[i]]>Size[Hson[u]]) Hson[u]=V[i];
    }
    return;
}

void dfs2(int u,int nowtop)
{
    Top[u]=nowtop;
    Id[u]=++idcnt;
    if (Hson[u]!=0) dfs2(Hson[u],nowtop);
    for (int i=Head[u];i!=-1;i=Next[i])
        if (V[i]!=Hson[u])
            dfs2(V[i],V[i]);
    return;
}

void TCAdd(int pos)//将pos到根的路径上的每一条边+1
{
    while (Top[pos]!=1)
    {
        SegModify(1,1,n,Id[Top[pos]],Id[pos],1);
        pos=Fa[Top[pos]];
    }
    SegModify(1,1,n,1,Id[pos],1);
    return;
}

int TCQuery(int pos)//询问pos到根的路径上的权值之和
{
    int ret=0;
    while (Top[pos]!=1)
    {
        ret=(ret+SegQuery(1,1,n,Id[Top[pos]],Id[pos])%Mod)%Mod;
        pos=Fa[Top[pos]];
    }
    ret=(ret+SegQuery(1,1,n,1,Id[pos])%Mod)%Mod;
    return ret;
}

void SegModify(int now,int l,int r,int ql,int qr,int delta)//线段树区间修改
{
    PushDown(now,l,r);
    if ((l==ql)&&(r==qr))
    {
        Seg[now]=(Seg[now]+(ll)(r-l+1)*(ll)delta%Mod)%Mod;
        Lazy[now]+=delta;
        return;
    }
    int mid=(l+r)/2;
    if (qr<=mid) SegModify(now*2,l,mid,ql,qr,delta);
    else if (ql>mid) SegModify(now*2+1,mid+1,r,ql,qr,delta);
    else
    {
        SegModify(now*2,l,mid,ql,mid,delta);
        SegModify(now*2+1,mid+1,r,mid+1,qr,delta);
    }
    Seg[now]=(Seg[now*2]+Seg[now*2+1])%Mod;
    return;
}

int SegQuery(int now,int l,int r,int ql,int qr)//线段树区间查询
{
    PushDown(now,l,r);
    if ((ql==l)&&(qr==r))
        return Seg[now]%Mod;
    int mid=(l+r)/2;
    if (qr<=mid) return SegQuery(now*2,l,mid,ql,qr)%Mod;
    if (ql>=mid+1) return SegQuery(now*2+1,mid+1,r,ql,qr)%Mod;
    return (SegQuery(now*2,l,mid,ql,mid)+SegQuery(now*2+1,mid+1,r,mid+1,qr))%Mod;
}

void PushDown(int now,int l,int r)//下放操作
{
    if (Lazy[now]==0) return;
    int mid=(l+r)/2;
    Seg[now*2]=(Seg[now*2]+(ll)Lazy[now]*(ll)(mid-l+1))%Mod;
    Seg[now*2+1]=(Seg[now*2+1]+(ll)Lazy[now]*(ll)(r-mid)%Mod);
    Lazy[now*2]=(Lazy[now*2]+Lazy[now])%Mod;
    Lazy[now*2+1]=(Lazy[now*2+1]+Lazy[now])%Mod;
    Lazy[now]=0;
    return;
}

void SegOutp(int now,int l,int r)
{
    PushDown(now,l,r);
    printf("[%d,%d] %d\n",l,r,Seg[now]);
    if (l==r) return;
    int mid=(l+r)/2;
    SegOutp(now*2,l,mid);
    SegOutp(now*2+1,mid+1,r);
    return;
}

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[BZOJ3626][LNOI2014]LCA(树链剖分,线段树)


HNCJ OIer 一枚