CodeForces Round #136(220B) - Little Elephant and Array

本题的关键之处在于发现10^5中~~最多小于450个符合要求的x.这种情况是1+2+3+4+....+n<=100000....得n<450...如此问题就大大简单了....首先找出这450个数..然后用h[100000][450] 来记录这些能符合要求的数在个个位置的和情况...构造h][]的大致需要10^5*450=4.5*10^7次操作~~可以接受
那么查询就非常快了..因为已经做好了这450个数在1~i ( 1 <= i <= n ) 的个数...每次询问~就只要看这450个数在这个区间的个数就行了~~

Program:
[cpp]
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<stack>
#define ll long long
#define oo 1000000000
#define pi acos(-1)
using namespace std;
struct node
{
     int x,num;
}a[100005];
int n,t,m,k,i,j,s[100005],b[450],h[100005][450];
map<int,int> mymap;
int main()
{
     while (~scanf("%d%d",&n,&t))
     {
             mymap.clear();
             m=0;
             for (i=1;i<=n;i++) scanf("%d",&s[i]);
             for (i=1;i<=n;i++)
             {
                   if (mymap.find(s[i])==mymap.end())
                   {
                          mymap[s[i]]=++m;
                          a[m].x=s[i];
                          a[m].num=0;
                   }
                   a[mymap[s[i]]].num++;
             }
             k=0;
             for (i=1;i<=m;i++)
                 if (a[i].x<=a[i].num)
                     b[++k]=a[i].x;
             for (i=1;i<=k;i++)
             {
                   h[0][i]=0;
                   for (j=1;j<=n;j++)
                      if (s[j]==b[i]) h[j][i]=h[j-1][i]+1;
                         else h[j][i]=h[j-1][i];
             }
             int l,r,ans;
             while (t--)
             {
                    ans=0;
                    scanf("%d%d",&l,&r);
                    for (i=1;i<=k;i++)
                        if (h[r][i]-h[l-1][i]==b[i]) ans++;
                    printf("%d\n",ans);
             }
     }
     return 0;
}

补充：软件开发 , C++ ,