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; 
}