记录编号	440968	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	迷妹	最终得分	100
用户昵称	+1s	是否通过	通过
代码语言	C++	运行时间	6.567 s
提交时间	2017-08-24 13:32:49	内存使用	10.23 MiB

#include<fstream>
using namespace std;
ifstream fin("fans.in");
ofstream fout("fans.out");
int n,q,a[100010];
struct{int l,r,a1,a2,a3;}stree[500050];
void bui(int l,int r,int idx)
{
	stree[idx].l=l;
	stree[idx].r=r;
	stree[idx].a1=0;
	stree[idx].a2=0;
	stree[idx].a3=0;
	if(l==r)
	{
		switch(a[l])
		{
			case 1:
			stree[idx].a1=1;
			break;
			case 2:
			stree[idx].a2=1;
			break;
			case 3:
			stree[idx].a3=1;
			break;
		}
		return;
	}
	int m=(l+r)/2;
	bui(l,m,idx*2);
	bui(m+1,r,idx*2+1);
	stree[idx].a1=stree[idx*2].a1+stree[idx*2+1].a1;
	stree[idx].a2=stree[idx*2].a2+stree[idx*2+1].a2;
	stree[idx].a3=stree[idx*2].a3+stree[idx*2+1].a3;
}
int qry1(int l,int r,int idx)
{
	if(stree[idx].l==0&&stree[idx].r==0)return 0;
	if(stree[idx].l==l&&stree[idx].r==r)return stree[idx].a1;
	if(r<=stree[idx*2].r)return qry1(l,r,idx*2);
	else if(l>=stree[idx*2+1].l)return qry1(l,r,idx*2+1);
	else return qry1(l,stree[idx*2].r,idx*2)+qry1(stree[idx*2+1].l,r,idx*2+1);
}
int qry2(int l,int r,int idx)
{
	if(stree[idx].l==0&&stree[idx].r==0)return 0;
	if(stree[idx].l==l&&stree[idx].r==r)return stree[idx].a2;
	if(r<=stree[idx*2].r)return qry2(l,r,idx*2);
	else if(l>=stree[idx*2+1].l)return qry2(l,r,idx*2+1);
	else return qry2(l,stree[idx*2].r,idx*2)+qry2(stree[idx*2+1].l,r,idx*2+1);
}
int qry3(int l,int r,int idx)
{
	if(stree[idx].l==0&&stree[idx].r==0)return 0;
	if(stree[idx].l==l&&stree[idx].r==r)return stree[idx].a3;
	if(r<=stree[idx*2].r)return qry3(l,r,idx*2);
	else if(l>=stree[idx*2+1].l)return qry3(l,r,idx*2+1);
	else return qry3(l,stree[idx*2].r,idx*2)+qry3(stree[idx*2+1].l,r,idx*2+1);
}
int faq()
{
	fin>>n>>q;
	for(int i=1;i<=n;i++)fin>>a[i];
	bui(1,n,1);
	for(int i=1;i<=q;i++)
	{
		int l,r;
		fin>>l>>r;
		fout<<qry1(l,r,1)<<' '<<qry2(l,r,1)<<' '<<qry3(l,r,1)<<endl;
	}
}
int xx=faq();
int main(){
return 0;
}