学步园

http://blog.csdn.net/acm_ted/article/details/7943188

题意：一个n个数字的数字序列，同时有m次询问，问在a,b之间符合数字x刚好出现x次的数有多少个。

题解：由于符合条件的数总数不超过450个，我们可以从此下手，先统计每个数字出现的次数，剔除不可能符合条件的数字，然后h[i][j]表示第i个数字在0~j出现的次数，询问的时候只要对i个数字将0~a-1和0~b两个区间内第i个数出现的次数相减就得到第i个数字在a~b中出现的次数，统计即可。

代码：

#include<cstdio>
#include<cstring>
#include<map>
#define MAX 100005
using namespace std;
struct node
{
    int x,num;
} temp;
int s[MAX],b[450],h[MAX][450];
map<int,struct node> mat;
int main()
{
    int n,m,k,t;
    for(; ~scanf("%d%d",&n,&t);)
    {
        mat.clear();
        for(int i=1; i<=n; ++i)
        {
            scanf("%d",&s[i]);
            //统计一个数出现的次数
            if(mat.count(s[i])==0)
            {
                temp.x=s[i];
                temp.num=1;
                mat.insert(make_pair(s[i],temp));
            }
            else
                (mat.find(s[i])->second.num)++;
        }
        k=0;
        //查找可能符合条件的数
        for(map<int,struct node>::iterator it=mat.begin(); it!=mat.end(); ++it)
            if(it->second.x<=it->second.num)  b[++k]=it->second.x;
        for (int i=1; i<=k; ++i)
        {
            h[0][i]=0;
            for (int 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;
        for(;t--;)
        {
            ans=0;
            scanf("%d%d",&l,&r);
            for (int i=1; i<=k; ++i)
                if (h[r][i]-h[l-1][i]==b[i]) ans++;
            printf("%d\n",ans);
        }
    }
    return 0;
}