AtCoder AGC #017 : C - Snuke and Spells

Dで時間を溶かして過去最低順位をやらかした。
http://agc017.contest.atcoder.jp/tasks/agc017_c

問題

N要素の整数列Aが与えられる。

Aの要素がx個の場合、要素xが同時に消える、という処理を繰り替えし、Aを完全に消すことを考える。
Aが初期状態で消しきれない場合、最小で何要素書き換えれば消しきれるかを考える。

Aの要素が1つずつクエリによって書き換わっていくとする。
書き換えた後のAについて、適宜上記消しきるまでの最小書き換え要素数を答えよ。

解法

A中で値xを持つ要素がF(x)個あったとする。
この場合、Aの要素がx個の場合x-F(x)個に遷移できる。
つまり、各xに対し閉区間[x-F(x),x]を考えよう。

これらが[0,N]をすべて覆うなら、全要素を消しきれる。そうでない場合、消しきれない。
各区間の長さの総和はNなので、消しきれない、すなわち[0,N]のうち覆われていない領域があれば、他の領域に複数の区間で多重におおわれている領域があるはずである。
よってそれらの領域を値の書き換えによって重複をなくし、その分覆われていない領域を覆うことができる。

あとは各クエリによっておおわれていない領域の数を数えよう。
クエリによってA[i]がx→yに書き換わるとき、F(x)が1減ってF(y)が1増えるので(変化前のF(x),F(y)に対し)[x-F(x),x-F(x)+1]の範囲の覆いが1つ減り、[y-(F(y)+1),y-F(y)]の範囲の覆いが1つ増える。
これにより両領域の覆いが0→1または1→0になったかどうかを考えていけば、1クエリO(1)で処理できる。

int N,M;
int A[202020];
int X[202020],Y[202020];

int num[202020];

int buf[404040];
int* cover=&buf[202020];
int ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	FOR(i,N) {
		cin>>A[i];
		num[A[i]]++;
	}
	for(i=1;i<=N;i++) {
		cover[i+1]--;
		cover[i+1-num[i]]++;
	}
	
	for(i=-200000;i<=N;i++) {
		cover[i]+=cover[i-1];
		if(i>=1 && cover[i]==0) ret++;
	}
	
	
	FOR(i,M) {
		cin>>X[i]>>Y[i];
		x=A[X[i]-1];
		cover[x+1-num[x]]--;
		if(cover[x+1-num[x]]==0 && x+1-num[x]>=1) ret++;
		num[x]--;
		
		x=Y[i];
		A[X[i]-1]=x;
		num[x]++;
		cover[x+1-num[x]]++;
		if(cover[x+1-num[x]]==1 && x+1-num[x]>=1) ret--;
		
		cout<<ret<<endl;
	}
}

まとめ

区間による被覆を考えるというアイデアはなかった…。