记录编号	358248	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[東方] 博丽灵梦 梦想妙珠	最终得分	100
用户昵称	喵喵喵	是否通过	通过
代码语言	C++	运行时间	0.834 s
提交时间	2016-12-15 11:24:04	内存使用	2.98 MiB

#include <cstdio>
#include <vector>
#define maxn 100010
using namespace std;

struct node{
	int i, k, p;
};

vector <node> e[maxn];
int n, m, a[maxn], c[maxn << 1], ans[maxn];

void solve(int l, int r){
	if(l == r) {
		for(int i = 0;i < e[r].size();i ++) 
			if(e[r][i].k == a[r])
				ans[e[r][i].i] += e[r][i].p;
		return;
	}
	int mid = (l + r) >> 1;
	for(int i = l;i <= mid;i ++)
		c[a[i]] ++;
	for(int i = mid + 1;i <= r;i ++)
		for(int j = 0;j < e[i].size();j ++)
			ans[e[i][j].i] += c[e[i][j].k] * e[i][j].p;
	for(int i = l;i <= mid;i ++)
		c[a[i]] --;
	solve(l, mid), solve(mid + 1, r);
}

int main() {
	freopen("mengxiangmiaozhu.in", "r", stdin);
    freopen("mengxiangmiaozhu.out", "w", stdout);
	int i, l, r, k;
	scanf("%d", &n);
	for(i = 1;i <= n;i ++)
		scanf("%d", &a[i]);
	scanf("%d", &m);
	for(i = 1;i <= m;i ++) {
		scanf("%d %d %d", &l, &r, &k);
		e[r].push_back((node){i, k, 1});
		e[l - 1].push_back((node){i, k, -1});
	}
	solve(1, n);
	for(i = 1;i <= m;i ++)
		printf("%d\n", ans[i]);
	return 0;
}