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

· · 题解

讲一下后缀平衡树的做法。

昨天花了一个下午写了一个 O(n\log^2 n) 的做法，怎么卡都卡不过去。 脑子想一想两只log怎么过五十万

第 k 大可以不用管它，因为其实你把大小关系排好后，加一个 dfs 序主席树和树上路径前缀主席树就行了。

那么我们考虑如何比较两个人的聪明程度。

首先，这可以倍增。我们哈希一下，暴力跳到两个点权值不一样的祖先，然后按照题意模拟即可。

但是显然，这种方法不能 O(1) 比较，瓶颈在比较两个父亲谁更聪明上。

这样的话，其实能想到后缀平衡树。话说刚学的东西都能忘掉，我也是厉害。

Owen友情提示：不要没看懂题面就说题目简单，分分钟打脸

我们直接暴力插进平衡树就行了。出题人用的是树上 SA，你可以去问他具体怎么做的。

zsy2K是怎么写完的

Code\ Below: 
// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
const double alpha=0.75;
int n,q,fa[maxn],a[maxn],rnk[maxn],ch[maxn][2],siz[maxn],s[maxn],top,rt;double val[maxn];
int st[maxn],ed[maxn],mp[maxn],tim,head[maxn],to[maxn],nxt[maxn],tot;

inline void addedge(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    st[x]=++tim;mp[tim]=x;
    for(int i=head[x];i;i=nxt[i]) dfs(to[i]);
    ed[x]=tim;
}
inline bool cmp(int x,int y)
{
    if(a[x]!=a[y]) return a[x]>a[y];
    if(fa[x]&&fa[y]&&fa[x]!=fa[y]) return val[fa[x]]<val[fa[y]];
    return x>y;
}
void build(int &x,int l,int r,double _l,double _r)
{
    if(l>r) {x=0;return;}
    int mid=(l+r)>>1;val[x=s[mid]]=(_l+_r)/2;siz[x]=r-l+1;
    build(ch[x][0],l,mid-1,_l,val[x]);
    build(ch[x][1],mid+1,r,val[x],_r);
}
void recycle(int &x)
{
    if(!x) return ;
    recycle(ch[x][0]);s[++top]=x;recycle(ch[x][1]);x=0;
}
void rebuild(int &x,double l,double r)
{
    top=0;recycle(x);build(x,1,top,l,r);
}
void insert(int &x,int y,double l,double r,bool f)
{
    if(!x) {x=y;siz[y]=1;val[y]=(l+r)/2;return;}
    bool fg=f;siz[x]++;
    if(cmp(y,x))
    {
        fg|=(alpha*siz[x]<=siz[ch[x][0]]+1);
        insert(ch[x][0],y,l,val[x],fg);
    }
    else
    {
        fg|=(alpha*siz[x]<=siz[ch[x][1]]+1);
        insert(ch[x][1],y,val[x],r,fg);
    }
    if(fg&&!f) rebuild(x,l,r);
}

struct CT
{
int rt[maxn],sz,ls[maxn*20],rs[maxn*20],siz[maxn*20];
void update(int &x,int y,int l,int r,int k)
{
    x=++sz;ls[x]=ls[y];rs[x]=rs[y];siz[x]=siz[y]+1;
    if(l == r) return ;
    int mid=(l+r)>>1;
    if(k <= mid) update(ls[x],ls[y],l,mid,k);
    else update(rs[x],rs[y],mid+1,r,k);
}
int query(int u,int v,int l,int r,int k)
{
    if(l == r) return l;
    int mid=(l+r)>>1,now=siz[ls[v]]-siz[ls[u]];
    if(k <= now) return query(ls[u],ls[v],l,mid,k);
    else return query(rs[u],rs[v],mid+1,r,k-now);
}
void dfs(int x,int f)
{
    rt[x]=rt[f];update(rt[x],rt[x],1,n,rnk[x]);
    for(int i=head[x];i;i=nxt[i]) dfs(to[i],x);
}
inline void init1() {dfs(1,0);}
inline void init2()
{
    for(int i=1;i<=n;i++) rt[i]=rt[i-1],update(rt[i],rt[i],1,n,rnk[mp[i]]);
}
inline int ask1(int x,int k) {return s[query(0,rt[x],1,n,k)];}
inline int ask2(int x,int k) {return s[query(rt[st[x]-1],rt[ed[x]],1,n,k)];}
}S,T;

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=2;i<=n;i++) scanf("%d",&fa[i]),addedge(fa[i],i);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),insert(rt,i,0,1,0);
    top=0;recycle(rt);
    for(int i=1;i<=n;i++) rnk[s[i]]=i;
    dfs(1);S.init1();T.init2();
    int op,x,k;
    while(q--)
    {
        scanf("%d%d",&op,&x);
        if(op==1) printf("%d\n",rnk[x]);
        if(op==2) scanf("%d",&k),printf("%d\n",S.ask1(x,k));
        if(op==3) scanf("%d",&k),printf("%d\n",T.ask2(x,k));
    }
    return 0;
}