\(x = 1,\ldots,N\) それぞれについて、 \(A_i = x\) なる \(i\) を昇順に管理した配列を \(\mathrm{idx}_x\) とします。

このとき、各クエリは以下のように言い換えられます。

\(L,R,X\) が与えられる。 \(\mathrm{idx}_X\) の要素のうち、 \(L\) 以上 \(R\) 以下のものは何個あるか答えよ。

このクエリは \(\mathrm{idx}_X\) の要素のうち \(L\) 以上の最小の要素は前から何番目か、\(R + 1\) 以上の最小の要素は前から何番目かを求めることで解くことができ、これらは二分探索により \(\mathrm{Ο}(\log N)\) で求められます。

計算量は \(\mathrm{Ο}(N+Q\log N)\) です。

実装例 (C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;

	vector<vector<int>> idx(n + 1);
	for(int i = 0; i < n; i++) {
		int a;
		cin >> a;
		idx[a].push_back(i);
	}

	int q;
	cin >> q;

	while(q--) {
		int l, r, x;
		cin >> l >> r >> x;
		cout << lower_bound(idx[x].begin(), idx[x].end(), r) - lower_bound(idx[x].begin(), idx[x].end(), l - 1) << endl;
	}
}