POJ2985 The K-th Lagest Group
どう見てもデータ構造ゲー。とりあえずグループにするということでUnion-findをつくる。
BITでもつかって「n匹以下が属するグループ数」の累積和をもっといてやると通る。
オーダーはO(m log^2 n)。
#include<stdio.h> #include<vector> #include<algorithm> int par[200000]; int ran[200000]; int ren[200000]; void init() { for(int i=0;i<200000;i++) { par[i]=i; ran[i]=0; ren[i]=1; } } int find(int a) { if(par[a]==a) { return a; } else { return par[a]=find(par[a]); } } void unite(int a,int b) { a=find(a); b=find(b); if(a==b) { return; } if(ran[a]>ran[b]) { par[b]=a; ren[a]+=ren[b]; } else { par[a]=b; ren[b]+=ren[a]; } if(ran[a]==ran[b]) { ran[b]++; } } int bit[262145]; void init2() { for(int i=0;i<262144;i++) { bit[i]=0; } } void add(int a,int b) { for(;;) { bit[a]+=b; a+=a&-a; if(a>200001) { break; } } } int sum(int a) { int gou=0; for(;;) { gou+=bit[a]; a-=a&-a; if(a==0) { break; } } return gou; } int main() { int cat,query; scanf("%d%d",&cat,&query); init(); init2(); add(1,cat); int gro=cat; for(int i=0;i<query;i++) { int whi; scanf("%d",&whi); if(whi==0) { int a,b; scanf("%d%d",&a,&b); a--; b--; a=find(a); b=find(b); if(find(a)!=find(b)) { add(ren[a],-1); add(ren[b],-1); add(ren[a]+ren[b],1); unite(a,b); gro--; } } else { int ban; scanf("%d",&ban); int beg=1,end=cat; int mok=gro-ban+1; for(;;) { int med=(beg+end)/2; if(sum(med)<mok) { beg=med+1; } else { end=med; } if(beg==end) { printf("%d\n",beg); break; } } } } }