记录编号	404193	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	迷妹	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	1.163 s
提交时间	2017-05-13 07:35:53	内存使用	7.56 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,q;
int ql,qr;
int N[100001],Q[4];
struct stree
{
	int l,r;
	int sum[4];
	stree(){l=0;r=0;memset(sum,0,sizeof(sum));}
}tree[300001];
void build(int l,int r,int now)
{
	int mid=(l+r)/2;
	tree[now].l=l;tree[now].r=r;
	if(l==r)
	{
		tree[now].sum[N[l]]++;
		return;
	}
	build(l,mid,2*now);
	build(mid+1,r,2*now+1);
	tree[now].sum[1]=tree[2*now].sum[1]+tree[2*now+1].sum[1];
	tree[now].sum[2]=tree[2*now].sum[2]+tree[2*now+1].sum[2];
	tree[now].sum[3]=tree[2*now].sum[3]+tree[2*now+1].sum[3];
}
void search(int l,int r,int now)
{
	int mid=(tree[now].l+tree[now].r)/2;
	if(tree[now].l==l&&tree[now].r==r)
	{
		Q[1]+=tree[now].sum[1];
		Q[2]+=tree[now].sum[2];
		Q[3]+=tree[now].sum[3];
		return;
	}
	if(r<=mid)
	{
		search(l,r,2*now);
		return;
	}
	if(l>mid)
	{
		search(l,r,2*now+1);
		return;
	}
	search(l,mid,2*now);
	search(mid+1,r,2*now+1);
}
int main()
{
	freopen("fans.in","r",stdin);
	freopen("fans.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&N[i]);
	}
	build(1,n,1);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&ql,&qr);
		search(ql,qr,1);
		printf("%d %d %d\n",Q[1],Q[2],Q[3]);
		Q[1]=0;Q[2]=0;Q[3]=0;
	}
	return 0;
}