这题之前写过线段树合并，今天复习Splay的时候想起这题，打算写一次Splay+启发式合并。
好爽！！！
写了长长的代码（其实也不长），只凭着下午的一点记忆（没背板子。。。），调了好久好久，过了样例，submit，1A！
哇真的舒服
调试输出懒得删了QwQ
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> #define ll long long #define which(x) (son[fq[x]][1]==x) using namespace std; const int maxn=500010,extar[2]={-2147483647,2147483647}; int n,m,x,y,z,tot,q,cnt; int fa[maxn],data[maxn],size[maxn],a[maxn],son[maxn][2],fq[maxn],id[maxn],root[maxn]; char ch[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} int search(int x,int k) { //printf("KPM%d %d %d ",x,k,son[x][1]); if(data[x]<k&&son[x][1])return search(son[x][1],k); if(data[x]>k&&son[x][0])return search(son[x][0],k); return x; } void rotate(int x) { int f=fq[x];bool k=which(x); son[f][k]=son[x][!k]; son[x][!k]=f; son[fq[f]][which(f)]=x; fq[x]=fq[f]; fq[f]=x; if(son[f][k])fq[son[f][k]]=f; size[x]=size[f]; size[f]=size[son[f][0]]+size[son[f][1]]+1; //printf("%d %d %d ORZCZL ",x,f,size[x]); } void splay(int x) { while(fq[x]) { int f=fq[x]; if(!fq[f]) { rotate(x); break; } if(which(x)^which(f))rotate(x); else rotate(f); rotate(x); } } void insert(int &x,int w) { //printf("%d %d ",x,w); if(!x){x=++tot;data[tot]=a[w];size[tot]=1;id[x]=w;return;} int k=search(x,a[w]); //printf("qiguai%d %d %d ",k,a[w],data[k]); //printf("QAQ"); ++tot; data[tot]=a[w];fq[tot]=k;id[tot]=w; if(a[w]<data[k])son[k][0]=tot; else son[k][1]=tot; size[tot]=1; while(k)size[k]++,k=fq[k]; splay(tot); x=tot; } int rank(int x,int k) { //++cnt; //printf("%d %d %d ",x,k,size[son[x][0]]); //if(cnt>10)exit(0); if(size[son[x][0]]>=k)return rank(son[x][0],k); if((size[son[x][0]]+1)==k)return x; return rank(son[x][1],k-size[son[x][0]]-1); } void merge(int x,int y) { //printf("WUWUWU%d %d ",x,y); if(son[x][0])merge(son[x][0],root[y]); insert(root[y],id[x]); if(son[x][1])merge(son[x][1],root[y]); } int main() { read(n);read(m); for(int i=1;i<=n;i++) { read(a[i]); fa[i]=i; } //for(int i=1;i<=n;i++)printf("OAO%d ",gf(i)); for(int i=1;i<=m;i++) { read(x);read(y); fa[gf(x)]=gf(y); } //for(int i=1;i<=n;i++)printf("QAQ%d %d ",gf(i),root[gf(i)]); //printf(" "); for(int i=1;i<=n;i++)insert(root[gf(i)],i); //for(int i=1;i<=n;i++)printf("QAQ%d %d ",gf(i),root[gf(i)]); //printf("%dQQQQQQQQQQQQQQ ",son[root[gf(1)]][0]); read(q); for(int i=1;i<=q;i++) { scanf("%s",ch);read(x);read(y); if(ch[0]=='Q') { x=gf(x); //printf("%d %d ",root[x],size[root[x]]); if(size[root[x]]<y)printf("-1 "); else { int pos=rank(root[x],y); printf("%d ",id[pos]),splay(pos),root[x]=pos; } } else { x=gf(x);y=gf(y); if(x!=y) { //printf("%d %d %d %d ",root[x],root[y],size[root[x]],size[root[y]]); if(size[root[x]]>size[root[y]])swap(x,y); fa[x]=y; merge(root[x],y); root[x]=0; } } } return 0; }
UPD：改了下insert
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> #define ll long long #define which(x) (son[fq[x]][1]==x) using namespace std; const int maxn=500010,extar[2]={-2147483647,2147483647}; int n,m,x,y,z,tot,q,cnt; int fa[maxn],data[maxn],size[maxn],a[maxn],son[maxn][2],fq[maxn],id[maxn],root[maxn]; char ch[maxn]; void read(int &k) { int f=1;k=0;char c=getchar(); while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar(); k*=f; } int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);} int search(int x,int k) { if(data[x]<k&&son[x][1])return search(son[x][1],k); if(data[x]>k&&son[x][0])return search(son[x][0],k); return x; } void rotate(int x) { int f=fq[x];bool k=which(x); son[f][k]=son[x][!k]; son[x][!k]=f; son[fq[f]][which(f)]=x; fq[x]=fq[f]; fq[f]=x; if(son[f][k])fq[son[f][k]]=f; size[x]=size[f]; size[f]=size[son[f][0]]+size[son[f][1]]+1; } void splay(int x) { while(fq[x]) { int f=fq[x]; if(!fq[f]) { rotate(x); break; } if(which(x)^which(f))rotate(x); else rotate(f); rotate(x); } } void insert(int &x,int w,int f) { if(!x) { x=++tot; data[x]=a[w]; size[x]=1; id[x]=w; fq[x]=f; return; } if(a[w]<data[x])insert(son[x][0],w,x); else insert(son[x][1],w,x); size[x]++; } int rank(int x,int k) { if(size[son[x][0]]>=k)return rank(son[x][0],k); if((size[son[x][0]]+1)==k)return x; return rank(son[x][1],k-size[son[x][0]]-1); } void merge(int x,int y) { if(son[x][0])merge(son[x][0],root[y]); insert(root[y],id[x],0);splay(tot);root[y]=tot; if(son[x][1])merge(son[x][1],root[y]); } int main() { read(n);read(m); for(int i=1;i<=n;i++) { read(a[i]); fa[i]=i; } for(int i=1;i<=m;i++) { read(x);read(y); fa[gf(x)]=gf(y); } for(int i=1;i<=n;i++)insert(root[gf(i)],i,0),splay(tot),root[gf(i)]=tot; read(q); for(int i=1;i<=q;i++) { scanf("%s",ch);read(x);read(y); if(ch[0]=='Q') { x=gf(x); if(size[root[x]]<y)printf("-1 "); else { int pos=rank(root[x],y); printf("%d ",id[pos]),splay(pos),root[x]=pos; } } else { x=gf(x);y=gf(y); if(x!=y) { if(size[root[x]]>size[root[y]])swap(x,y); fa[x]=y; merge(root[x],y); root[x]=0; } } } return 0; }