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

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

#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);
}
}
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(){
for (int i=1;i<=n;i++) F[i]=i,root[i]=i;
for (int i=1;i<=m;i++){
merge(x1,y1);
}
while (Q--){
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;
}