求助,样例TLE

回复帖子

@Fee_cle6418  2018-12-22 10:14 回复
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int c[500005][2],fa[500005],sum[500005],data[500005];
int n,m,q,tot=0,ans=0;
int f[500005];
int GetFa(int x){
    return x==f[x]?x:f[x]=GetFa(f[x]);
}
void PushUp(int x){
    sum[x]=sum[c[x][0]]+sum[c[x][1]]+1;
}
void Rotate(int x){
    int y=fa[x],z=fa[y],l,r;
    l=(c[y][0]!=x);
    r=l^1;
    if(z){
        if(c[z][0]==y)c[z][0]=x;
        else c[z][1]=x;
    }
    fa[x]=z;
    fa[y]=x;
    fa[c[x][r]]=y;
    c[y][l]=c[x][r];
    c[x][r]=y;
    PushUp(y);
    PushUp(x);
}
void Splay(int x){
    while(fa[x]){
        int y=fa[x],z=fa[y];
        if(z){
            if((c[y][0]==x)^(c[z][0]==y))Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
}
void Insert(int x,int k){
    int p,f;
    Splay(p=x);
    while(p){
        f=p;
        sum[p]++;
        if(data[x]<=data[p])p=c[p][0];
        else p=c[p][1];
    }
    if(data[x]<=data[f])c[f][0]=x;
    else c[f][1]=x;
    fa[x]=f;
    sum[x]=1;
    c[x][0]=c[x][1]=0;
    Splay(x);
}
int Find(int x,int k){
    Splay(x);
    if(sum[x]<k)return -1;
    while(1){
        if(sum[c[x][0]]+1==k)return x;
        if(sum[c[x][0]]>=k)x=c[x][0];
        else {
            k-=sum[c[x][0]]+1;
            x=c[x][1];
        }
    }
}
void Init(){
    for(int i=1;i<=n;i++){
        f[i]=i;
        sum[i]=1;
    }
}
void DFS(int x,int t){
    if(c[x][0])DFS(c[x][0],t);
    if(c[x][1])DFS(c[x][1],t);
    Insert(x,t);
}
void Merge(int a,int b){
    if(GetFa(a)==GetFa(b))return;
    Splay(a);Splay(b);
    if(sum[a]>sum[b])swap(a,b);
    f[GetFa(a)]=GetFa(b);
    DFS(a,b);
}
int main(){
    scanf("%d%d",&n,&m);
    Init();
    for(int i=1;i<=n;i++){
        scanf("%d",&data[i]);
    }
//  Insert(2,1);return 0;
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        Merge(x,y);
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        char opt[2];
        int x,y;
        scanf("%s%d%d",opt,&x,&y);
        if(opt[0]=='B')Merge(x,y);
        else printf("%d\n",Find(x,y));
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。