Codeforces #233 Div1. D. Instant Messanger

だいぶ面倒な問題。
http://codeforces.com/contest/398/problem/D

問題

N人の人がいる。
２人の関係は友人であるかないかのどちらかであり、その関係は双方向的である。
初期状態でM組の友人となる２人組が与えられる。

ここで、あるチャットシステムに対し、以下のQ個のクエリに答えよ。

• チャットにu番の人が参加する。
• チャットからu番の人が退室する。
• ある２人組が新規に友人となる。
• ある２人組が友人関係をやめる。
• u番と友人関係にある人のうち、参加中の人数を答える。

解法

友人関係は高々M+Q通りである。
よって多数の友人を持つ人は限られている。
そこで平方分割で少数の友人を持つ人と多数の友人を持つ人を分けて管理しよう。
それぞれ、各自の友人一覧をunordered_setで管理する。
ただし、少数の友人を持つ人は、自身のunordered_setには多数の友人を持つ友人を入れない。

チャット参加・不参加クエリについては、少数の友人を持つ人は友人に参加・不参加人数を更新する。
多数の友人を持つ人は更新をしない(クエリ時にオンデマンドで人数を数える)。

友人関係の追加削除はそのまま愚直に行う。
平方分割の境界人数を跨ぐような友人人数の変更に注意する。

最後の参加中の友人数のカウントだが、少数の友人を持つ人が持つ、少数の友人を持つ友人については、チャット参加・不参加クエリの段階でカウント済みである。
あとは多数の友人を持つ人は少ないので、それぞれが自分の友人であるか、また参加中であるかを数え上げればよい。

const int D=555;
int N,M,Q;
int state[50500],cnt[50500];
unordered_set<int> F[50500],H[50500];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>M>>Q;
	cin>>i;
	while(i--) cin>>y, state[y-1]=1;
	while(M--) {
		cin>>x>>y;
		F[x-1].insert(y-1);
		F[y-1].insert(x-1);
	}

	FOR(i,N) {
		if(state[i]&&F[i].size()<D) ITR(it,F[i]) cnt[*it]++;
		if(F[i].size()>=D) ITR(it,F[i]) H[*it].insert(i);
	}

	while(Q--) {
		cin>>s>>x;
		x--;
		if(s[0]=='O' || s[0]=='F') {
			if(F[x].size()<D) {
				if(s[0]=='O') { ITR(it,F[x]) cnt[*it]++;}
				if(s[0]=='F') { ITR(it,F[x]) cnt[*it]--;}
			}
			state[x]^=1;
		}
		else if(s[0]=='A') {
			cin>>y;
			y--;
			if(F[x].size()==D-1) {
				ITR(it,F[x]) {
					cnt[*it]-=state[x];
					H[*it].insert(x);
				}
			}
			if(F[y].size()==D-1) {
				ITR(it,F[y]) {
				cnt[*it]-=state[y];
				H[*it].insert(y);
				}
			}
			F[x].insert(y);
			F[y].insert(x);
			if(F[x].size()<D) cnt[y]+=state[x];
			else H[y].insert(x);
			if(F[y].size()<D) cnt[x]+=state[y];
			else H[x].insert(y);
		}
		else if(s[0]=='D') {
			cin>>y;
			y--;
			if(F[x].size()<D) cnt[y]-=state[x];
			else H[y].erase(x);
			if(F[y].size()<D) cnt[x]-=state[y];
			else H[x].erase(y);
			F[x].erase(y);
			F[y].erase(x);

			if(F[x].size()==D-1) {
				ITR(it,F[x]) H[*it].erase(x), cnt[*it]+=state[x];
			}
			if(F[y].size()==D-1) {
				ITR(it,F[y]) H[*it].erase(y), cnt[*it]+=state[y];
			}
		}
		else {
			int ret=cnt[x];
			ITR(it,H[x]) if(state[*it]) ret++;
			cout<<ret<<endl;
		}
	}

}

まとめ

面倒だけど平方分割ってことが分かればすんなりだね。