P5346 【XR-1】柯南家族(后缀数组+主席树)

佚名 7年前 (2019-05-06) 随笔 1763人围观抢沙发百度已收录

题目

P5346 【XR-1】柯南家族

做法

聪明性是具有传递性的，且排列是固定的
那么先预处理出每个点的名次，用主席树维护\(k\)大值

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

一眼平衡树，遍历的同时插入\(O(log^2n)\)，总时间复杂度\(O(nlog^2n)\)

显然还需要优化，考虑两个点的比较：按深度递减比较值，如果在等长前提下值相等，则比较深度最浅且的不一样的祖先的大小

这和后缀比较大小相似，我们后缀数组来实现排列的这个过程

Code

#include<bits/stdc++.h>
typedef int LL;
const LL maxn=1e6+9;
inline LL Read(){
    LL x(0),f(1); char c=getchar();
    while(c<'0' || c>'9'){
        if(c=='-') f=-1; c=getchar();
    }
    while(c>='0' && c<='9'){
        x=(x<<3)+(x<<1)+c-'0'; c=getchar();
    }return x*f;
}
struct node{
    LL to,nxt;
}dis[maxn];
LL n,num,q,m,tim;
LL head[maxn],fa[maxn],a[maxn],sa[maxn],x[maxn],y[maxn],z[maxn],c[maxn],rk[maxn],inc[maxn][25],b[maxn],dfn[maxn],low[maxn];
inline void Add(LL u,LL v){
    dis[++num]=(node){v,head[u]}; head[u]=num;
}
inline void Sort(){
    for(LL i=1;i<=n;++i) ++c[x[i]=a[i]];
    for(LL i=2;i<=m;++i) c[i]+=c[i-1];
    for(LL i=n;i>=1;--i) sa[c[x[i]]--]=i;
    for(LL i=1;i<=n;++i) rk[sa[i]]=i;
    for(LL len=1,t=0;len<n;len<<=1,++t){
        LL num(0);
        for(LL i=1;i<=n;++i) z[i]=rk[inc[i][t]];
        for(LL i=0;i<=n;++i) c[i]=0;
        for(LL i=1;i<=n;++i) ++c[z[i]]; for(LL i=1;i<=n;++i) c[i]+=c[i-1];
        for(LL i=n;i>=1;--i) y[c[z[sa[i]]]--]=sa[i];
        
        for(LL i=0;i<=m;++i) c[i]=0;
        for(LL i=1;i<=n;++i) ++c[x[i]]; for(LL i=1;i<=m;++i) c[i]+=c[i-1];
        for(LL i=n;i>=1;--i) sa[c[x[y[i]]]--]=y[i];
        for(LL i=1;i<=n;++i) rk[sa[i]]=i;
        std::swap(x,y);
        x[sa[1]]=num=1;
        for(LL i=2;i<=n;++i)
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]] && y[inc[sa[i]][t]]==y[inc[sa[i-1]][t]])?num:++num;
        if(num==n) break;
        m=num;
    }
}
struct Tree{
    LL root[maxn],nod,size[maxn*10],son[maxn*10][2];
    void Update(LL &now,LL pre,LL l,LL r,LL x){
        now=++nod; size[now]=size[pre]+1;
        if(l==r) return; LL mid(l+r>>1);
        if(x<=mid){ Update(son[now][0],son[pre][0],l,mid,x); son[now][1]=son[pre][1]; }
        else{ Update(son[now][1],son[pre][1],mid+1,r,x); son[now][0]=son[pre][0]; }
    }
    LL Query1(LL now,LL l,LL r,LL k){
        if(l==r) return sa[l]; LL mid(l+r>>1);
        LL ret(size[son[now][0]]);
        return k<=ret?Query1(son[now][0],l,mid,k):Query1(son[now][1],mid+1,r,k-ret);
    }
    LL Query2(LL pre,LL now,LL l,LL r,LL k){
        if(l==r) return sa[l]; LL mid(l+r>>1);
        LL ret(size[son[now][0]]-size[son[pre][0]]);
        return k<=ret?Query2(son[pre][0],son[now][0],l,mid,k):Query2(son[pre][1],son[now][1],mid+1,r,k-ret);
    }
}T1,T2;
void Fir(LL u){
    inc[u][0]=fa[u];
    for(LL i=1;i<=20;++i){
        inc[u][i]=inc[inc[u][i-1]][i-1]; if(!inc[u][i]) break;
    }
    for(LL i=head[u];i;i=dis[i].nxt) Fir(dis[i].to);
}
void Dfs(LL u){
    dfn[u]=++tim;
    T1.Update(T1.root[u],T1.root[fa[u]],1,n,rk[u]);
    T2.Update(T2.root[tim],T2.root[tim-1],1,n,rk[u]);
    for(LL i=head[u];i;i=dis[i].nxt) Dfs(dis[i].to);
    low[u]=tim;
}
inline void Init(){
    n=Read(); q=Read();
    for(LL i=2;i<=n;++i) Add(fa[i]=Read(),i);
    for(LL i=1;i<=n;++i) b[i]=a[i]=Read();
    std::sort(b+1,b+1+n); m=std::unique(b+1,b+1+n)-b-1;
    for(LL i=1;i<=n;++i) a[i]=std::lower_bound(b+1,b+1+m,a[i])-b;
}
int main(){
    Init();
    Fir(1);
    Sort();
    std::reverse(sa+1,sa+1+n);
    for(LL i=1;i<=n;++i) rk[sa[i]]=i;
    Dfs(1);
    while(q--){
        LL op(Read()),x(Read());
        if(op==1) printf("%d\n",rk[x]);
        else{
            LL k(Read());
            if(op==2) printf("%d\n",T1.Query1(T1.root[x],1,n,k));
            else printf("%d\n",T2.Query2(T2.root[dfn[x]-1],T2.root[low[x]],1,n,k));
        }
    }
    return 0;
}