记录编号	405162	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[東方] 博丽灵梦 梦想妙珠	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	1.672 s
提交时间	2017-05-15 20:38:30	内存使用	1.84 MiB

# include <bits/stdc++.h>
# define MAXN 200003
# define mid ((l + r) >> 1)
using namespace std;
inline int gn() {
	int k = 0, f = 1;
	char c = getchar();
	for(; !isdigit(c); c= getchar()) if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}
struct node {
	int sum;
	node *ls, *rs;
	inline node() {
		sum = 0;
		ls = rs = NULL;
	}
}*root[MAXN];
node *build(int l, int r) {
	node *x = new node();
	if(l == r) {
		x->sum = 0;
		return x;
	} else {
		x->ls = build(l, mid);
		x->rs = build(mid + 1, r);
		return x;
	}
}
node *insert(node *pre, int l, int r, int p) {
	node *x = new node();
	if(l == r) {
		x->sum = pre->sum + 1;
	} else {
		if(p <= mid) {
			x->ls = insert(pre->ls, l, mid, p);
			x->rs = pre->rs;
		} else {
			x->ls = pre->ls;
			x->rs = insert(pre->rs, mid + 1, r, p);
		}
	}
	return x;
}
int query(node *x, int l, int r, int c) {
	if(l > r) return 0;
	if(l == r) return x->sum;
	else if(c <= mid) return query(x->ls, l, mid, c);
	else if(c > mid) return query(x->rs, mid + 1, r, c);
}
int a[MAXN], maxa, n, nn, m;
int main() {
	freopen("mengxiangmiaozhu.in", "r", stdin);
	freopen("mengxiangmiaozhu.out", "w", stdout);
	n = gn();
	for(int i = 1; i <= n; i++) {
		a[i] = gn();
		maxa = max(maxa, a[i]);
	}
	root[0] = build(1, maxa);
	for(int i = 1 ; i <= n; i++) {
		root[i] = insert(root[i - 1], 1, maxa, a[i]);
	}
	m = gn();
	while(m--) {
		int l = gn();
		int r = gn();
		int c = gn();
		if(c > maxa) {
			printf("0\n");
			continue;
		}
		int tl = query(root[l - 1], 1, maxa, c);
		int tr = query(root[r], 1, maxa, c);
		printf("%d\n", tr - tl);
	}
}