记录编号	481196	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[東方] 博丽灵梦 梦想妙珠	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.865 s
提交时间	2018-01-01 19:40:07	内存使用	47.59 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200010;
int n,m,sz,a[maxn],tr[maxn],lc[maxn*20],rc[maxn*20],sum[maxn*20];
void insert(int &x,int last,int l,int r,int d){
	x=++sz;
	if(l==r)sum[x]=sum[last]+1;
	else{
		lc[x]=lc[last],rc[x]=rc[last];
		int mid=(l+r)>>1;
		if(d<=mid)insert(lc[x],lc[last],l,mid,d);
		else insert(rc[x],rc[last],mid+1,r,d);
	}
}
int query(int x,int last,int l,int r,int d){
	if(l==r)return sum[x]-sum[last];
	int mid=(l+r)>>1;
	if(d<=mid)return query(lc[x],lc[last],l,mid,d);
	else return query(rc[x],rc[last],mid+1,r,d);
}
int main(){
	freopen("mengxiangmiaozhu.in","r",stdin);
	freopen("mengxiangmiaozhu.out","w",stdout);
	scanf("%d",&n);
	int p=0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),p=max(p,a[i]);
	for(int i=1;i<=n;i++)insert(tr[i],tr[i-1],1,p,a[i]);
	scanf("%d",&m);
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		if(z>p)printf("0\n");
		else printf("%d\n",query(tr[y],tr[x-1],1,p,z));
	}
	return 0;
}