BZOJ-1803: Spoj1487 Query on a tree III

[文章目录]

Description

You are given a node-labeled rooted tree with n nodes. Define the query (x, k): Find the node whose label is k-th largest in the subtree of the node x. Assume no two nodes have the same labels.1 <= n <= 10^5

转换为dfs序上的区间第k大,之后主席树即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000 
int n,m,a[N],b[N],id[N];
struct seg
{
    int ls,rs,s;
}t[N*20];
int se,rt[N];
void insert(int &r1,int r2,int l,int r,int x)
{
    r1=++se; t[r1].s=t[r2].s+1;
    if(l==r) return ;
    int mid=(l+r)>>1;
    if(x<=mid) t[r1].rs=t[r2].rs,insert(t[r1].ls,t[r2].ls,l,mid,x);
    else t[r1].ls=t[r2].ls,insert(t[r1].rs,t[r2].rs,mid+1,r,x);
}
int query(int r1,int r2,int l,int r,int x)
{
    if(l==r) return id[l];
    int mid=(l+r)>>1;
    if(x<=t[t[r2].ls].s-t[t[r1].ls].s) return query(t[r1].ls,t[r2].ls,l,mid,x);
    x-=(t[t[r2].ls].s-t[t[r1].ls].s);
    return query(t[r1].rs,t[r2].rs,mid+1,r,x);
}
int head[N],to[N<<1],nxt[N<<1],cnt;
inline void add(int x,int y)
{
    to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
int tim,in[N],out[N],siz[N];
void dfs(int x,int pre)
{
    in[x]=++tim; insert(rt[tim],rt[tim-1],1,n,a[x]);
    for(int i=head[x];i;i=nxt[i]) if(to[i]!=pre)
        dfs(to[i],x),siz[x]+=siz[to[i]];
    out[x]=tim; siz[x]++;
}
int main()
{
    scanf("%d",&n); int i;
    for(i=1;i<=n;++i) scanf("%d",a+i),b[i]=a[i];
    sort(b+1,b+n+1);
    for(i=1;i<=n;++i) id[a[i]=lower_bound(b+1,b+n+1,a[i])-b]=i;
    int x,y;
    for(i=2;i<=n;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    dfs(1,0);
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",query(rt[in[x]-1],rt[out[x]],1,n,y));
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注