本文共 3395 字，大约阅读时间需要 11 分钟。
//模拟赛里一道题要启发式合并，但我没想出来，我记得以前写过，结果发现原来是用线段树合并做的。。。
线段树合并：
#include #include #include #include #include #include #include #include #include #include #include #include typedef long long LL;using namespace std;const int N=100010;int n,m,q,fa[N],root[N],ls[N<<6],rs[N<<6],sum[N<<6],id[N],rk[N],cnt;char s[10];int read() { int d=0,f=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=(d<<3)+(d<<1)+c-48,c=getchar(); return d*f;}void judge(){freopen(".in","r",stdin); freopen(".out","w",stdout);}int ask(int x){ return fa[x]==x?x:fa[x]=ask(fa[x]);}void insert(int &k,int l,int r,int x){ if (!k) k=++cnt; sum[k]++; if (l==r) return; int mid=(l+r)>>1; if (x<=mid) insert(ls[k],l,mid,x); else insert(rs[k],mid+1,r,x);}int query(int k,int l,int r,int x){ if (l==r) return l; int mid=(l+r)>>1; if (sum[ls[k]]>=x) return query(ls[k],l,mid,x); else return query(rs[k],mid+1,r,x-sum[ls[k]]);}int merge(int x,int y){ if (!x) return y; if (!y) return x; ls[x]=merge(ls[x],ls[y]); rs[x]=merge(rs[x],rs[y]); sum[x]=sum[ls[x]]+sum[rs[x]]; return x;}int main(){ //judge(); n=read(); m=read(); for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=n;i++) rk[i]=read(); while (m--) { int x=read(),y=read(); fa[ask(x)]=ask(y); } for (int i=1;i<=n;i++) { insert(root[ask(i)],1,n,rk[i]); id[rk[i]]=i; } q=read(); while (q--) { scanf("%s",s); int x=read(),y=read(); if (s[0]=='Q') { int q=ask(x); if (sum[root[q]]
splay启发式合并：
#include #include #include #include #include #include #include #include #include #include #include #define mp make_pair#define pb push_backusing namespace std;typedef long long LL;typedef pair pa;const int N=100010;int n,m,fa[N],f[N],c[N][2],siz[N],a[N],tmp,b[N],cnt;//vector e[N];int Write[20],WRI;inline void judge(){freopen(".in","r",stdin);freopen(".out","w",stdout);}inline int read(){ int d=0,f=1; char c=getchar(); while (c<'0'||c>'9'){ if (c=='-') f=-1; c=getchar();} while (c>='0'&&c<='9') d=d*10+c-48,c=getchar(); return d*f;}inline void write(int x){ if (!x){putchar('0'); return;}if (x<0) putchar('-'),x=-x;for (WRI=1;x;x/=10,WRI++) Write[WRI]=x%10;for (int i=WRI-1;i;i--) putchar((char)(Write[i]+48));}inline int ask(int x){ return f[x]==x?x:f[x]=ask(f[x]);}inline void update(int x){siz[x]=siz[c[x][0]]+siz[c[x][1]]+1;}inline void rotate(int x,int &k){ int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; if (y==k) k=x; else c[z][c[z][1]==y]=x; fa[c[x][r]]=y; fa[x]=z; fa[y]=x; c[y][l]=c[x][r]; c[x][r]=y; update(y); update(x);}inline void splay(int x,int &k){ while (x!=k) { int y=fa[x],z=fa[y]; if (y!=k) c[y][0]==x^c[z][0]==y?rotate(x,k):rotate(y,k); rotate(x,k); }}inline void insert(int x,int y){ c[y][0]=c[y][1]=0; siz[y]=1; for (;;) { if (a[y] =k) x=c[x][0]; else k-=siz[c[x][0]]+1,x=c[x][1]; } return res;}int main(){ //judge(); n=read(); m=read(); for (int i=1;i<=n;i++) a[i]=read(),f[i]=i,siz[i]=1; for (int i=1;i<=m;i++) Unite(read(),read()); m=read(); while (m--) { char s[2]; scanf("%s",s); int x=read(),y=read(); if (s[0]=='B') Unite(x,y); else printf("%d\n",query(ask(x),y)); } return 0;}
转载于:https://www.cnblogs.com/lujiaju6555/p/8522148.html
