记录编号	406133	评测结果	WEEEEEEEEEEEEEEEEEEE
题目名称	[東方] 博丽灵梦 梦想妙珠	最终得分	0
用户昵称	JustWB	是否通过	未通过
代码语言	C++	运行时间	2.214 s
提交时间	2017-05-17 21:37:59	内存使用	1.07 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cctype>
using namespace std;
struct pstree
{
	int l,r;
	int ls,rs;
	int sum,mx;
	pstree(){l=0,r=0,ls=-1,rs=-1,sum=0,mx=0;}
};
int n,q,mx,maxn;
int ver[100001];
int N[100001];
vector<pstree> tree;
inline int read()
{
	char temp;
	int tmp=0;
	while(temp=getchar())
	{
		if(isdigit(temp))tmp=tmp*10+(temp-48);
		else return tmp;
	}
}
inline int build(int l,int r)
{
	pstree temp;
	tree.push_back(temp);
	int now=maxn++;
	tree[now].l=l;tree[now].r=r;
	if(l==r)
	{
		tree[now].mx=l;
		return now;
	}
	int mid=(l+r)/2,ls,rs;
	ls=build(l,mid);
	tree[now].ls=ls;
	rs=build(mid+1,r);
	tree[now].rs=rs;
	tree[now].mx=max(tree[tree[now].ls].mx,tree[tree[now].rs].mx);;
	return now;
}
inline int change(int des,int now)
{
	pstree temp;
	temp=tree[now];
	tree.push_back(temp);
	int ve=maxn++;
	if(tree[ve].l==tree[ve].r)
	{
		tree[ve].sum++;
		return ve;
	}
	int mid=tree[tree[ve].ls].r,tem;
	if(des<=mid)
	{
		tem=change(des,tree[ve].ls);
		tree[ve].ls=tem;
	}
	else 
	{
		tem=change(des,tree[ve].rs);
		tree[ve].rs=tem;
	}
	return ve;
}
inline int search(int des,int now)
{
	if(des>tree[now].mx)return 0;
	if(tree[now].l==tree[now].r)return tree[now].sum;
	int mid=tree[tree[now].ls].r;
	if(des<=mid)return search(des,tree[now].ls);
	else return search(des,tree[now].rs);
}
int main()
{
	freopen("mengxiangmiaozhu.in","r",stdin);
	freopen("mengxiangmiaozhu.out","w",stdout);
	n=read();
	for(int i=1;i<=n;i++)
	{
		N[i]=read();
		if(N[i]>mx)mx=N[i];
	}
	ver[0]=build(1,mx);
	for(int i=1;i<=n;i++)ver[i]=change(N[i],ver[i-1]);
	q=read();
	for(int i=1;i<=q;i++)
	{
		int l=read(),r=read(),c=read();
		printf("%d\n",search(c,ver[r])-search(c,ver[l-1]));
	}
	return 0;
}