1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
|
#include<cstdio> #define mp make_pair #define pb push_back using namespace std; typedef long long LL; inline LL read() { LL 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<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } const int N=300008; int n,m; int op,x,y; int p[N],p1,p2; int a[N],bit[N]; int num; int l,r,mid,k,ans; inline void add(int pos,int x) { for(int i=pos;i<=n;i+=i&-i){ bit[i]+=x; } } inline int sum(int pos) { int tmp=0; for(int i=pos;i;i-=i&-i){ tmp+=bit[i]; } return tmp; } inline int find(int x) { return x==p[x]?x:p[x]=find(p[x]); } int main() { n=read();m=read(); for(int i=1;i<=n;++i){ p[i]=i; } for(int i=1;i<=n;++i){ a[i]=1; } add(1,n); num=n; while(m--){ op=read(); if(op==0){ x=read();y=read(); p1=find(x); p2=find(y); if(p1==p2) continue; add(a[p1],-1); add(a[p2],-1); add(a[p2]=a[p1]+a[p2],1); p[p1]=p2; --num; } else{ k=read(); k=num-k+1; l=1; r=n; while(l<=r){ mid=(l+r)>>1; if(sum(mid)>=k){ r=mid-1; ans=mid; } else{ l=mid+1; } } printf("%dn",ans); } } return 0; }
|
近期评论