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

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100010;
struct Q{
	int l,r,c,id,belong;
	bool operator<(const Q &q)const{
		if(belong!=q.belong)return belong<q.belong;
		return r<q.r;
	}
}q[maxn];
int n,B,m,a[maxn],l,r,cnt[maxn<<1]={0},ans[maxn];
int main(){
	freopen("mengxiangmiaozhu.in","r",stdin);
	freopen("mengxiangmiaozhu.out","w",stdout);
	scanf("%d",&n);
	B=(int)(sqrt(n)+0.5);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].c);
		q[i].belong=(q[i].l-1)/B+1;
		q[i].id=i;
	}
	sort(q+1,q+m+1);
	l=r=1;cnt[a[1]]=1;
	for(int i=1;i<=m;i++){
		if(l>q[i].l)for(int k=l-1;k>=q[i].l;k--)cnt[a[k]]++;
		if(r<q[i].r)for(int k=r+1;k<=q[i].r;k++)cnt[a[k]]++;
		if(l<q[i].l)for(int k=l;k<q[i].l;k++)cnt[a[k]]--;
		if(r>q[i].r)for(int k=r;k>q[i].r;k--)cnt[a[k]]--;
		ans[q[i].id]=cnt[q[i].c];
		l=q[i].l;r=q[i].r;
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
}