记录编号	433204	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	迷妹	最终得分	100
用户昵称	yymxw	是否通过	通过
代码语言	C++	运行时间	3.324 s
提交时间	2017-08-05 08:09:40	内存使用	0.98 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
inline int read()
{
  int x=0,f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9')
  {
    if(ch=='-')
      f=-1;
    ch=getchar();
  }
  while(ch>='0'&&ch<='9')
  {
    x=(x<<3)+(x<<1)+ch-'0';
    ch=getchar();
  }
  return x*f;
}
struct node
{
  int yi,er,san;
  node(){yi=0;er=0;san=0;}
};
int n,m,x,y,len;
int match[100010],a[100010],zhong[1000],hao[1000],xi[1000];
node query(int x,int y)
{
	node ans;
  if(match[x]+1>=match[y])
  {
    for(int i=x;i<=y;++i)
    {
      if(a[i]==1)
        ans.yi++;
      if(a[i]==2)
        ans.er++;
      if(a[i]==3)
        ans.san++;
    }
  }
  else
  {
    for(int i=x;i;++i)
    {
      if(match[x]!=match[i])
        break;
      if(a[i]==1)
        ans.yi++;
      if(a[i]==2)
        ans.er++;
      if(a[i]==3)
        ans.san++;
    }
    for(int i=y;i;--i)
    {
      if(match[i]!=match[y])
        break;
      if(a[i]==1)
        ans.yi++;
      if(a[i]==2)
        ans.er++;
      if(a[i]==3)
        ans.san++;
    }
    for(int i=match[x]+1;i<=match[y]-1;++i)
    {
      ans.yi+=zhong[i];
      ans.er+=hao[i];
      ans.san+=xi[i];
    }
  }
  return ans;
}
int main()
{
	freopen("fans.in","r",stdin);
	freopen("fans.out","w",stdout);
  n=read();m=read();
  len=(int)sqrt(n+0.5);
  for(int i=1;i<=n;++i)
    a[i]=read();
  for(int i=1;i<=n;++i)
    match[i]=(i-1)/len+1;
  for(int i=1;i<=match[n];++i)
    for(int j=(i-1)*len+1;j<=min(i*len,n);++j)
    {
      if(a[j]==1)
        zhong[i]++;
      if(a[j]==2)
        hao[i]++;
      if(a[j]==3)
        xi[i]++;
    }
  //for(int i=1;i<=match[n];++i)
    //cout<<"i="<<i<<" "<<zhong[i]<<" "<<hao[i]<<" "<<xi[i]<<endl;
  for(int i=1;i<=m;++i)
  {
    x=read();y=read();
    node e=query(x,y);
    printf("%d %d %d\n",e.yi,e.er,e.san);
  }
  return 0;
}