Vjudge19.12.15哈理工学校試合

A快速べき乗テンプレート問題
Bはセット+木状配列の問題を調べた:初期状況はn個のギャングがあり、2つの操作がある:2つのギャングを合併し、k番目のギャングの人数を尋ねる.各人が属するギャングを集計して維持し,樹状配列でi人のギャングの個数を残すことができる.ツリー配列テンプレートは次のとおりです.

int lowbit(int x){
	return x&(-x);
}
void update(int i,int k){
	while(i<=n){
		c[i]+=k;
		i+=lowbit(i);
	}
}
int getsum(int i){
	int res=0;
	while(i>0){
		res+=c[i];
		i-=lowbit(i);
	}
	return res;
}
int find_kth(int k){//  k 
	int ans=0, cnt=0;
	for(int i=20;i>=0;i--){
		ans+=(1<<i);
		if(ans>=n||cnt+c[ans]>=k){
			ans-=(1<<i);
		}else{
			cnt+=c[ans];
		}
	}
	return ans+1;
}

主なコード:

	update(a[fx], -1);
	update(a[fy], -1);
	update(a[fx]+a[fy], 1);
	fa[fx]=fy;
	a[fy]+=a[fx];
	num--;

C D E F G H I模擬問題Jサイン問題