4448: [Scoi2015]情报传递|主席树|离线操作

能够把全部的操作离线，然后树链剖分将全部人搜集情报的时间增加到主席树中，查询的时候能够直接查询搜集情报时间≤i−C[i]−1的人的个数

时间复杂度n∗log22n，空间复杂度n∗log2n

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<vector>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define ll long long

#define N 202020

using namespace std;

int sc()

{

    int i=0,f=1; char c=getchar();

    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}

    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();

    return i*f;

}

int opt[N],X[N],Y[N],C[N];

int sum[N*20],ch[N*20][2],tim[N],root[N];

int fa[N],top[N],size[N],deep[N],S[N],wh[N];

int head[N],nxt[N],lst[N];

int n,m,tot,cnt,num;

void insert(int x,int y)

{

    lst[++tot]=y;nxt[tot]=head[x];head[x]=tot;

}

void dfs(int x)

{

    size[x]=1;

    for(int i=head[x];i;i=nxt[i])

    {

        deep[lst[i]]=deep[x]+1;

        fa[lst[i]]=x;

        dfs(lst[i]);

        size[x]+=size[lst[i]];

    }

}

void _dfs(int x,int htp)

{

    int k=0;S[x]=++cnt;top[x]=htp;wh[cnt]=x;

    for(int i=head[x];i;i=nxt[i])

        if(size[lst[i]]>size[k])k=lst[i];

    if(!k)return ;_dfs(k,htp);

    for(int i=head[x];i;i=nxt[i])

        if(lst[i]!=k)_dfs(lst[i],lst[i]);

}

void add(int pre,int &x,int l,int r,int v)

{

    if(!x)x=++num;

    sum[x]=sum[pre]+1;

    if(l==r)return;

    int mid=l+r>>1;

    if(v<=mid)

        ch[x][1]=ch[pre][1],

        add(ch[pre][0],ch[x][0],l,mid,v);

    else

        ch[x][0]=ch[pre][0],

        add(ch[pre][1],ch[x][1],mid+1,r,v);

}

int query(int x,int y,int c)

{

    int L=root[x-1],R=root[y],l=1,r=m,res=0;

    while(l!=r)

    {

        int mid=l+r>>1;

        if(c<=mid)

            L=ch[L][0],R=ch[R][0],r=mid;

        else

            res+=sum[ch[R][0]]-sum[ch[L][0]],

            L=ch[L][1],R=ch[R][1],l=mid+1;

    }

    res+=(c>=l?sum[R]-sum[L]:0);

    return res;

}

void solve(int x,int y,int c)

{

    int sum=0,res=deep[x]+deep[y];

    while(top[x]!=top[y])

    {

        if(deep[top[x]]<deep[top[y]])swap(x,y);

        sum+=query(S[top[x]],S[x],c);x=fa[top[x]];

    }

    if(deep[x]<deep[y])swap(x,y);

    sum+=query(S[y],S[x],c);

    printf("%d %d\n",res-2*deep[y]+1,sum);

}

int main()

{

    n=sc();

    for(int i=1;i<=n;i++)

    {

        fa[i]=sc();

        if(fa[i])insert(fa[i],i);

    }

    dfs(1);_dfs(1,1);

    m=sc();

    for(int i=1;i<=m;i++)

    {

        opt[i]=sc();

        if(opt[i]==2)

            tim[sc()]=i;

        else X[i]=sc(),Y[i]=sc(),C[i]=sc();

    }

    for(int i=1;i<=n;i++)

        add(root[i-1],root[i],1,m,tim[wh[i]]?tim[wh[i]]:m);

    for(int i=1;i<=m;i++)

        if(opt[i]==1)

            solve(X[i],Y[i],i-C[i]-1);

    return 0;

}