萌新刚学splay 没能过样例 求大佬帮帮忙/kel

回复帖子

@CYW_lyr 2019-08-09 22:22 回复

样例第三个点一直输出0 感觉写的没问题啊/kel (这个splay调了2天了 zbl)

#include<bits/stdc++.h>
#define lc ch[x][0]
#define rc ch[x][1]
using namespace std;
const int maxn=100010;
int n,m,Q;
int a[maxn],F[maxn],fa[maxn],ch[maxn][2],siz[maxn],root[maxn];
void pushup(int x){
    siz[x]=siz[lc]+siz[rc]+1;
}
void rotate(int x){
    int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][k^1];
    if (z) ch[z][ch[z][1]==y]=x;ch[x][k^1]=y;ch[y][k]=w;
    if (w) fa[w]=y;fa[y]=x;fa[x]=z;
    pushup(y);pushup(x);
}
void splay(int x,int goal,int id){
    while (fa[x]!=goal){
        int y=fa[x],z=fa[y];
        if (z!=goal)
            rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
        rotate(x);
    }
    if (!goal) root[id]=x;
}
inline int kth(int root,int k){
    int x=root;
    while (1){
        if (siz[lc]>=k) x=lc;
            else if (siz[lc]+1<k) x=rc,k-=siz[lc]+1;
                else return x;
    }
}
inline void insert(int x,int &rt,int f){
    if (!rt){rt=x;fa[x]=f;siz[x]=1;return;}
    siz[rt]++;
    if (a[x]<=a[rt]) insert(x,ch[rt][0],rt);
    else insert(x,ch[rt][1],rt);
    pushup(rt);
}
inline int get(int x){if (F[x]!=x) F[x]=get(F[x]);return F[x];}
queue<int> q;
inline void merge(int x,int y){
    //连接x,y
    if (x==y) return;
    if (siz[root[x]]>siz[root[y]]) swap(x,y);//把x连到y上
    F[x]=y;q.push(root[x]);
    while (!q.empty()){
        int u=q.front();q.pop();
        if (ch[u][0]) q.push(ch[u][0]);
        if (ch[u][1]) q.push(ch[u][1]);
        insert(u,root[y],0);
        splay(u,root[y],y);
    }
}
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int main(){
    n=read();m=read();
    for (int i=1;i<=n;i++) a[i]=read();//rank
    for (int i=1;i<=n;i++) F[i]=i,root[i]=i;
    for (int i=1;i<=m;i++){
        int x=read(),y=read(),x1=get(x),y1=get(y);
        merge(x1,y1);
    }
    Q=read();
    while (Q--){
        char t=getchar();int x=read(),y=read();
        if (t=='Q'){
            if (siz[root[get(x)]]<y) puts("-1");
            else printf("%d\n",kth(root[get(x)],y));
        }
        else merge(get(x),get(y));
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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