Codeforces #588 Div1 C. Konrad and Company Evaluation

こっちも最終的には通ったけど手間をかけすぎた。
https://codeforces.com/contest/1229/problem/C

問題

N人の人がおり、初期スコアはi番目の人はiである。
ここでQ個のクエリが与えられる。各クエリでは人が1名指定され、その人のスコアが最大値となるように更新される。

ここで、N人の間には嫌いあう関係性の2人組がいくつかある。
互いに嫌いあう2名は、スコアの高い方が低い方に自慢する関係となる。
各クエリ後、3名のtuple(a,b,c)において、aがbに、bがcに自慢するようなケースは何通りあるか。

解法

この関係性をN頂点の有効グラフを考える。
スコアの高い方から低い方に辺を張るとする。
クエリで指定された点は、自身とつながる辺をすべて外向きにする。
また、求める組み合わせは、各頂点における入次数と出次数の積の総和である。

解法として平方分割を行う。
次数の少ない頂点に関しては、愚直に辺の向きを変えつつ隣接点の次数の積の変化を加算すればよい。
問題は次数の多い点を複数回指定された場合である。ただ考えてみると、同じ点が2回指定された場合、2回目に辺の向きを変えるのは、2回の間に向きを自頂点側に変えられた辺だけである。
よってそのような辺だけ覚えておけば、再度向きを変えるべき辺の数は少なく済む。

int N,M,Q;
int C[101010];
int in[101010],out[101010];
vector<int> E[101010];
set<int> U[101010];
 
int big[101010];
vector<int> B;
set<int> S[101010];
set<int> H[101010];
 
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) C[i]=i;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		if(x>y) swap(x,y);
		E[x].push_back(y);
		E[y].push_back(x);
		S[x].insert(y);
		S[y].insert(x);
		in[x]++;
		out[y]++;
		H[x].insert(y);
	}
	MINUS(big);
	FOR(i,N) if(E[i].size()>=3000) {
		B.push_back(i);
		big[i]=B.size()-1;
	}
	
	
	ll ret=0;
	FOR(i,N) ret+=1LL*in[i]*out[i];
	cout<<ret<<endl;
	
	cin>>Q;
	FOR(i,Q) {
		cin>>x;
		x--;
		ret-=1LL*in[x]*out[x];
		in[x]=0;
		out[x]=S[x].size();
		
		if(big[x]>=0) {
			FORR(e,H[x]) {
				if(C[e]>C[x]) {
					ret-=1LL*in[e]*out[e];
					in[e]++;
					out[e]--;
					ret+=1LL*in[e]*out[e];
					if(big[e]>=0) H[e].insert(x);
				}
			}
			H[x].clear();
		}
		else {
			FORR(e,E[x]) {
				if(C[e]>C[x]) {
					ret-=1LL*in[e]*out[e];
					in[e]++;
					out[e]--;
					ret+=1LL*in[e]*out[e];
					if(big[e]>=0) H[e].insert(x);
				}
			}
		}
		
		C[x]=101000+i;
		cout<<ret<<endl;
	}
}

まとめ

本番方針はすぐに思いついていたのに、バグを作りこむはBでヘマするわでひどい回だった。