Codeforces 190D Non-Secret Cypher

問題

数列a[i]が与えられる。
数列の連続する部分列(a[i], a[i+1], ... a[j])のうち、
同一の値をk個以上含むものの個数を求めよ。

制約条件

n≦4*10^5

方針

尺取。
mapで値の個数を数える。
iが左端、jが右端で、iからjの区間に含まれる同一の値の個数の最大値がk個を超えるまでjを動かす。

同一の値の個数を探すのを無理矢理set使ってやったけど、
「普通にk回以上出ている値は何種類か」を持つだけでよかった。

ソースコード

int n, k, a[400000];

int main(){
	scanf("%d%d", &n, &k);
	rep(i, n) scanf("%d", a + i);
	
	set<pi> s;
	map<int, int> cnt;
	ll ans = 0;
	for(int i = 0, j = 0; i < n; i++){
		while(j < n && -s.begin()->first < k){
			pi p = *s.begin();
			s.erase(p);
			cnt[a[j]]++;
			s.insert(mp(-cnt[a[j]], a[j]));
			j++;
		}
		if(s.size() && -s.begin()->first >= k) ans += n - j + 1;
		
		pi p = mp(-cnt[a[i]], a[i]);
		s.erase(p);
		cnt[a[i]]--;
		s.insert(mp(-cnt[a[i]], a[i]));
	}
	cout << ans << endl;
	return 0;
}