AtCoder ABC #293 : G - Triple Index

これは典型かな・・・
https://atcoder.jp/contests/abc293/tasks/abc293_g

問題

整数列Aが与えられる。
以下のクエリに答えよ。

• Aの部分列が指定される。同じ値を持つ3要素の組み合わせは何通りか。

解法

部分列の境界の伸び縮みに対し、組み合わせの数はO(1)で更新できる。
そこで、Mo's Algorithmでクエリを並べ替えて処理すればよい。

int N,Q;
int A[202020];
ll C[202020];
int L[202020],R[202020];
ll ret[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>Q;
	FOR(i,N) cin>>A[i];
	vector<vector<int>> E;
	FOR(i,Q) {
		cin>>L[i]>>R[i];
		L[i]--;
		E.push_back({L[i]/500,R[i],i});
	}
	
	int CL=0,CR=0;
	ll cur=0;
	sort(ALL(E));
	FORR(e,E) {
		int TL=L[e[2]];
		int TR=R[e[2]];
		while(TL<CL) {
			CL--;
			x=A[CL];
			cur+=C[x]*(C[x]-1)/2;
			C[x]++;
		}
		while(TR>CR) {
			x=A[CR];
			cur+=C[x]*(C[x]-1)/2;
			C[x]++;
			CR++;
		}
		while(TL>CL) {
			x=A[CL];
			C[x]--;
			cur-=C[x]*(C[x]-1)/2;
			CL++;
		}
		while(TR<CR) {
			CR--;
			x=A[CR];
			C[x]--;
			cur-=C[x]*(C[x]-1)/2;
		}
		ret[e[2]]=cur;
	}
	FOR(i,Q) cout<<ret[i]<<endl;
	
	
}

まとめ

なんかFより先にG解く人が多くて、問題見る前びっくりした。