Indeedなう（予選B） : D - 高橋くんと数列

こちらは問題文自体はちゃんと理解したものの、最初方針をミスしてこちらもタイムロス。
http://indeednow-qualb.contest.atcoder.jp/tasks/indeednow_2015_qualb_4

問題

N要素の数列A[i]が与えられる。
A中には1～Cの整数が最低１回は登場する。

ここで1～Cの各クエリに答えよ。
各クエリでは、入力値xに対し、Aの連続部分列A[l..r]が1つ以上xを含むような(l,r)の対の数を答えよ。

解法

Aの連続部分列の数はN*(N+1)/2である。
各クエリxにおいては、ここからxを含まない部分列の数を引けばよい。
仮にA[i]=xで、次にxとなる添え字がjである(A[j]=x)場合、i＜l≦r＜jとなる(l,r)はxを含まないので(j-i)*(j-i-1)/2を引けばよい。

最初に前処理でxの登場位置をvector等で一覧で持っておけば、全体でO(N+C)で処理できる。

ll N,C;
vector<int> E[101000];

void solve() {
	int i,j,k,l,r; ll x,y;

	cin>>N>>C;
	FOR(i,N+1) E[i].push_back(0);
	FOR(i,N) cin>>x, E[x].push_back(i+1);
	FOR(i,N+1) E[i].push_back(N+1);
	
	for(i=1;i<=C;i++) {
		ll num=N*(N+1)/2;
		FOR(x,E[i].size()-1) {
			y=E[i][x+1]-E[i][x]-1;
			num-=y*(y+1)/2;
		}
		cout<< num << endl;
	}
}

まとめ

解法ミスのタイムロスが痛かった。