Codeforces Round #120 (Div. 2) D : Non-Secret Cypher

acceptされたコード

長さN(<4*10^5)の数列がある。連続する部分列で、K回以上重複する要素があるものをすべて求める問題。

解法

両端の要素が同じでその範囲ではその数がちょうどK回現れるような区間を列挙する。その区間を右端でソートして小さい順に重複しないように数え上げていけば解ける。BITなどを使っても解けるっぽい？

acceptされたコード

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long int64;

const int MAX_N = (int)(4e5);

int N, K;
int as[MAX_N];
vector<int> xs[MAX_N];

void init(){
	scanf("%d%d", &N, &K);
	for(int i=0; i<N; ++i){
		scanf("%d", as+i);
	}
}

void compress(){
	vector<int> nums(as, as+N);
	sort(nums.begin(), nums.end());
	nums.erase(unique(nums.begin(), nums.end()), nums.end());
	for(int i=0; i<N; ++i){
		as[i] = distance(nums.begin(), lower_bound(nums.begin(), nums.end(), as[i]));
	}
}

struct range{
	int from, to;
	range(){}
	range(int from, int to):from(from), to(to){}
};

bool operator< (const range& lhs, const range& rhs){
	return lhs.to < rhs.to;
}

int64 solve(){
	int64 ans = 0;
	compress();

	for(int i=0; i<N; ++i){
		xs[as[i]].push_back(i);
	}

	vector<range> rs;
	for(int i=0; i<MAX_N; ++i){
		for(int j=0; j + K <= (int)xs[i].size(); ++j){
			rs.push_back( range(xs[i][j], xs[i][j+K-1]+1) );
		}
	}

	sort(rs.begin(), rs.end());

	int prev = -1;
	for(int i=0; i<(int)rs.size(); ++i){
		if(prev < rs[i].from){
			ans += (int64)(N - rs[i].to + 1) * (rs[i].from - prev);
		}
		prev = max(prev, rs[i].from);
	}

	return ans;
}

int main(){
	init();
	cout << solve() << endl;

	return 0;
}