题解 P5346 【【XR-1】柯南家族】

y2823774827y

2019-05-06 16:41:04

Solution

**更好的阅读体验$\Longrightarrow $[Blog](https://i.cnblogs.com/PostDone.aspx?postid=10820513&actiontip=%E4%BF%9D%E5%AD%98%E4%BF%AE%E6%94%B9%E6%88%90%E5%8A%9F)** ## 题目 [P5346 【XR-1】柯南家族](https://www.luogu.org/problemnew/show/P5346) ## 做法 聪明性是具有传递性的,且排列是固定的 那么先预处理出每个点的名次,用主席树维护$k$大值 一眼平衡树,遍历的同时插入$O(log^2n)$,总时间复杂度$O(nlog^2n)$ 显然还需要优化,考虑两个点的比较:按深度递减比较值,如果在等长前提下值相等,则比较深度最浅且的不一样的祖先的大小 这和后缀比较大小相似,我们后缀数组来实现排列的这个过程 ## Code ```cpp #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; } ```