CodeForces Round #136(220B) - Little Elephant and Array - c++编程基础

本题的关键之处在于发现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
#include
#include
#include
#include
#include
#include
#include
#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 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;
}