昨天做Tree Rotation,没发现自己写的是暴力，还要了数据。。。。。。
然后发现好像必须得用启发式合并
不想学线段树，学了个splay的
---------------------------------------------------
假设现在有n个点，每个点是一个splay,互不连起来
假设我们每次让两个不连通的splay联通，
所谓启发式：就是把小的合并到大的上，这样使复杂度有保证
怎么合并呢？就是先把小的splay的每个点找出来，然后插入到大的splay
---------------------------------------------------
这里我还理解了半天。。。
还以为跟可并堆什么的很像。。。没想到这么暴力（naive）
bzoj 2733
这道题我把Rank加反了，结果tle
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 400010 int n,m,Q; int size[N],fa[N],key[N],father[N],Rank[N],q[N]; int child[N][2]; int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') {x*=10; x=x+c-'0'; c=getchar();} return x*f; } void update(int x) { size[x]=size[child[x][0]]+size[child[x][1]]+1; } void zig(int x) { int y=fa[x]; fa[x]=fa[y]; child[fa[x]][child[fa[x]][1]==y]=x; child[y][0]=child[x][1]; fa[child[x][1]]=y; fa[y]=x; child[x][1]=y; update(y); update(x); } void zag(int x) { int y=fa[x]; fa[x]=fa[y]; child[fa[x]][child[fa[x]][1]==y]=x; child[y][1]=child[x][0]; fa[child[x][0]]=y; fa[y]=x; child[x][0]=y; update(y); update(x); } void splay(int x) { while(fa[x]) { int y=fa[x],z=fa[y]; if(!z) { child[y][0]==x?zig(x):zag(x); break; } child[y][0]==x?zig(x):zag(x); child[z][0]==x?zig(x):zag(x); } } void insert(int x,int root) { int y=root,last; while(y) { last=y; if(key[x]>key[y]) y=child[y][1]; else y=child[y][0]; } fa[x]=last; child[last][(key[x]>key[last])]=x; update(x); update(last); splay(x); } void merge(int x,int y) { splay(x); splay(y); if(size[x]>size[y]) swap(x,y); int l=1,r=0; q[++r]=x; while(l<=r) { int u=q[l++]; if(child[u][0]) q[++r]=child[u][0]; if(child[u][1]) q[++r]=child[u][1]; } q[0]=y; for(int i=1;i<=r;i++) insert(q[i],q[i-1]); } int findkth(int x,int k) { if(size[child[x][0]]==k-1) return x; if(size[child[x][0]]+1>k) return findkth(child[x][0],k); else return findkth(child[x][1],k-size[child[x][0]]-1); } int find(int x) { return father[x]==x?father[x]:find(father[x]); } void connect(int x,int y) { int a=find(x),b=find(y); if(a==b) return; if(Rank[a]>=Rank[b]) { Rank[a]+=Rank[b]; father[b]=a; } else { Rank[b]+=Rank[a]; father[a]=b; } } void link(int x,int y) { if(find(x)==find(y)) return; merge(x,y); connect(x,y); } void query(int x,int k) { splay(x); if(size[x]<k) { printf("-1 "); return; } printf("%d ",findkth(x,k)); } int main() { n=read(); m=read(); for(int i=1;i<=n;i++) { key[i]=read(); father[i]=i; Rank[i]=size[i]=1; } for(int i=1;i<=m;i++) { int u,v; u=read(); v=read(); if(u==0||v==0) continue; link(u,v); } Q=read(); while(Q--) { char s[10]; int a,b; scanf("%s",s); a=read(); b=read(); if(a==0||b==0) continue; if(s[0]=='B') link(a,b); if(s[0]=='Q') query(a,b); } return 0; }