Codeforces 180 E. Cubes

問題

n個の整数の列がある。それぞれの数は1以上m以下である。
この列から最大k個を取り除いて、同じ整数の続く部分の長さを最大にしたい。

同じ整数の続く部分の最大の長さを求めよ。

制約条件

n≦2*10^5
m≦10^5
k≦n

方針

長さlの区間を同じ整数だけにできるというのは、
その区間で最も多い整数をaとすると、aがl-k個以上あるということである。

値の種類ごとにバケットにわけて、インデックスを二分探索(or 尺取り）する。
インデックスの差が上の条件を満たす範囲を二分探索すればいい。

のだけれど、自分はsetを使って上の条件を使って直接尺取りした。
適切なデータ構造を使えば、最も多い整数の個数を取り出すことはO(log n)で出来るので。
また、条件を満たすかは左端を決めると単調になるので尺取りできる。

ソースコード

void run()
{
	cin >> n >> m >> k;
	rep(i,n) cin >> a[i], a[i]--;
	set<pi> s;
	rep(i,m) s.insert(mp(0, i)), cnt[i] = 0;
	
	int ans = 0;
	
	for(int i = 0, j = 0; i < n-k; i++){
		while(j < i) j++;
		while(j < n){
			int c = -s.begin()->first + (a[j] == s.begin()->second);
			
			if(c < j+1 - i - k) break;
			set<pi>::iterator it = s.lower_bound(mp(-cnt[a[j]], a[j]));
			s.erase(it);
			s.insert(mp(-(++cnt[a[j]]), a[j]));
			j++;
		}
		ans = max(ans, -s.begin()->first);
		
		set<pi>::iterator it = s.lower_bound(mp(-cnt[a[i]], a[i]));
		s.erase(it);
		s.insert(mp(-(--cnt[a[i]]), a[i]));
	}
	cout << ans << endl;
}