Codeforces 420 Coder-Strike 2014 - Finals (online edition, Div. 1) C. Bug in Code

問題

n人の人がいて、この中の二人が犯人。
n人のそれぞれに犯人は誰だと思うと聞いた結果、i番目の人はa[i]とb[i]と答えた。

犯人の候補(x, y)は、x = a[i]またはy = a[i]またはx = b[i]またはy = b[i]を満たすとき、
i番目の人の同意を得られる。
最低p人の同意を得られる犯人の候補はいくつあるか求めよ。

制約条件

n≦3*10^5
0≦p≦n
1≦a[i], b[i]≦n
a[i]≠b[i]かつa[i]≠i, b[i]≠i

方針

人を頂点、a[i], b[i]を辺とするグラフを考える。
最低p人の同意を得られる犯人の候補とは、ふたつの頂点(v1, v2)の組で、
p本の辺をカバーしているもの。

v1を固定して考える。
v1によりカバーされた辺はv2によって２度カバーされたと数えてはいけないので、
v1から出ている辺を削除しておく。
この後で、次数がp - d(v1)以上の頂点の数を数えればよい。

頂点を数えるのをまともにやるとTLEなので、
次数xの頂点がいくつあるかをbinary indexed treeに入れておけば、
BITに1回足したり引いたりするだけで、頂点の個数の管理ができる。

で、毎回これをやっても、
各辺につき2回ずつ削除と戻す操作が行われるだけなので、
時間計算量O(nlogn)とかになって間に合う。

ソースコード

const int MX = 300010;
int n, p;
int deg[MX], bit[MX];
vi e[MX];

ll sum(int i){
	ll res = 0;
	for(i++; i; i -= i & -i) res += bit[i];
	return res;
}
void add(int i, int x){
	for(i++; i < MX; i += i & -i) bit[i] += x;
}

int main(){
	scanf("%d%d", &n, &p);
	rep(i, n){
		int a, b;
		scanf("%d%d", &a, &b);
		e[a].pb(b);
		e[b].pb(a);
	}
	int cnt = 0;
	ll ans = 0;
	
	for(int i = 1; i <= n; i++){
		
		deg[i] = e[i].size();
		add(deg[i], 1);
	}
	
	for(int i = 1; i <= n; i++){
		
		rep(j, e[i].size()){
			add(deg[e[i][j]], -1);
			add(--deg[e[i][j]], 1);
		}
		if(deg[i] >= p) ans += n - 1;
		else{
			ans += n - 1 - sum(p - deg[i] - 1) + (deg[i] <= p - deg[i] - 1);
		}
		
		rep(j, e[i].size()){
			add(deg[e[i][j]], -1);
			add(++deg[e[i][j]], 1);
		}
	}
	cout << ans / 2 << endl;
	return 0;
}