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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1e5 + 10;

inline int in(void){ 
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp)) tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

struct NODE{ 
	int sum;
	NODE *ls, *rs;

	NODE(){ 
		ls = rs = NULL;
	}
};

NODE* Build(int l, int r);
NODE* change(NODE *pre, int k, int l, int r);
int query(NODE *ln, NODE *rn, int k, int L, int R);
inline int search(int *s, int k);

int a[MAXN], oa[MAXN];
int N, Q, n = 1;
NODE *roots[MAXN];

int main(){ 
#ifndef LOCAL
	freopen("mengxiangmiaozhu.in", "r", stdin);
	freopen("mengxiangmiaozhu.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	N = in();

	for(int i = 1; i <= N; ++i) oa[i] = a[i] = in();

	sort(oa + 1, oa + 1 + N);
	for(int i = 2; i <= N; ++i) if(oa[i] != oa[i - 1]) oa[++n] = oa[i];
	for(int i = 1; i <= N; ++i) a[i] = search(oa, a[i]);

	roots[0] = Build(1, n);

	for(int i = 1; i <= N; ++i) roots[i] = change(roots[i - 1], a[i], 1, n);

	Q = in();

	for(int i = 1, l, r, j, k; i <= Q; ++i){ 
		l = in(), r = in(), j = in();
		k = search(oa, j);
		if(j != oa[k]){ 
			printf("0\n");
			continue;
		}
		
		printf("%d\n", query(roots[l - 1], roots[r], k, 1, n));
	}
	return 0;
}

NODE* Build(int l, int r){ 
	NODE *p = new NODE();

	if(l != r){ 
		int mid = l + r >> 1;
		p->ls = Build(l, mid);
		p->rs = Build(mid + 1, r);
	}

	p->sum = 0;
	return p;
}

inline int search(int *s, int k){ 
	return lower_bound(s + 1, s + n + 1, k) - s;
}

NODE* change(NODE *pre, int k, int l, int r){ 
	NODE *p = new NODE();

	if(l == r) p->sum = pre->sum + 1;
	else{ 
		int mid = l + r >> 1;
		if(k <= mid){ 
			p->ls = change(pre->ls, k, l, mid);
			p->rs = pre->rs;
		}
		else{ 
			p->ls = pre->ls;
			p->rs = change(pre->rs, k, mid + 1, r);
		}

		p->sum = p->ls->sum + p->rs->sum;
	}

	return p;
}

int query(NODE *ln, NODE *rn, int k, int L, int R){ 
	if(L == R) return rn->sum - ln->sum;
	int mid = L + R >> 1;
	if(k <= mid) return query(ln->ls, rn->ls, k, L, mid);
	return query(ln->rs, rn->rs, k, mid + 1, R);
}