[cpp] /******************************************** 題目大意： n只貓，m個操作; 0 a b 合並兩個貓所在的集合; 1 k 詢問在當前的所有的集合中含有的貓的個數第k大的為多大; 算法思想： 合並操作應該用並查集; 查詢操作可以用線段樹; 開始將所有的數據輸入進來,利用並查集計算出所有種集合的大小; 然後根據集合的大小建樹查詢就可以了; *********************************************/ #include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<climits> #include<algorithm> using namespace std; #define L l,m,u<<1 #define R m+1,r,u<<1|1 const int N=200010; struct darling { int op;//操作判斷 int x,y; } d[N];//輸入數據 struct cat { int pre;//前驅結點 int rank;//並查集的高度，即貓的數量 } a[N]; struct Node { int l,r,s; } t[N*4];//線段樹 int vs1[N],vs2[N];//記錄每個集合裡面貓的數量,即rank int flag[N];//記錄每個結點的位置,方便線段樹插入 int cnt1,cnt2;//記錄集合的數量 int n,m; void Build(int l,int r,int u)//建樹 { t[u].l=l; t[u].r=r; t[u].s=0; if(l==r) return; int m=(l+r)>>1; Build(L); Build(R); } void Insert(int x,int n,int u)//插入結點 { if(t[u].l==t[u].r) { t[u].s+=n; return; } int m=(t[u].l+t[u].r)>>1; if(x<=m) Insert(x,n,u<<1); else Insert(x,n,u<<1|1); t[u].s=t[u<<1].s+t[u<<1|1].s; } int Query(int k,int u)//查詢 { if(t[u].l==t[u].r) { return t[u].l; } if(k>t[u<<1|1].s) return Query(k-t[u<<1|1].s,u<<1); return Query(k,u<<1|1); } void Init(int x)//初始化並查集 { for(int i=0; i<=x; i++) { a[i].pre=i; a[i].rank=1; } } int Find(int x)//查詢前驅結點 { if(a[x].pre!=x) return a[x].pre=Find(a[x].pre); return a[x].pre; } void Union(int x,int y)//合並操作 { x=Find(x); y=Find(y); if(x==y) return; if(a[x].rank>a[y].rank) { a[x].rank+=a[y].rank; vs1[++cnt1]=a[x].rank; a[y].pre=x; } else { a[y].rank+=a[x].rank; vs1[++cnt1]=a[y].rank; a[x].pre=y; } } void solve() { for(int i=0; i<m; i++) { if(d[i].op) { int v=Query(d[i].x,1); printf("%d\n",vs2[v]); } else { int x1=Find(d[i].x); int y1=Find(d[i].y); if(x1==y1) continue; int x2=a[x1].rank; int y2=a[y1].rank; if(x2==y2) { Insert(flag[x2],-2,1); } else { Insert(flag[x2],-1,1); Insert(flag[y2],-1,1); } Insert(flag[x2+y2],1,1); Union(x1,y1); } } } int main() { //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin); while(~scanf("%d%d",&n,&m)) { Init(n); vs1[1]=1; cnt1=1; for(int i=0; i<m; i++) { scanf("%d",&d[i].op); if(d[i].op) { scanf("%d",&d[i].x); } else { scanf("%d%d",&d[i].x,&d[i].y); Union(d[i].x,d[i].y); } } int cnt2=1; sort(vs1+1,vs1+cnt1+1); for(int i=2; i<=cnt1; i++)//記錄多少組不同 { if(vs1[i]!=vs1[cnt2]) vs1[++cnt2]=vs1[i]; } for(int i=1; i<=cnt2; i++) { flag[vs1[i]]=i; vs2[i]=vs1[i]; } Build(1,cnt2,1); Insert(1,n,1); Init(n); cnt1=0; solve(); } return 0; }
