codeforces 221D Little Elephant and Array

    题目的意思是说，给定一个区间，其长度为m，然后进行n次查询，每次查询给定区间[l,r]，查出区间中出现次数等于其值大小的数的个数。开始做的时候，不是超空间就是超时间，然后借鉴了一下别人的思路。

   首先使用一个a数组记录m个元素，期间用b数组记录每个元素出现的次数，然后在用l数组和r数组记录给定的查询区间，因为已经记录每个元素的出现次数，所以那些出现次数小于其值的数根本就不用考虑了，然后就是从1扫到m，扫的时候用s数组记录该值在每个位置及之前出现的次数，然后在逐一对每个区间进行判断就行了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[100010],b[100010],l[100010],r[100010],s[100010],ans[100010];
int main()
{
    int n,m;
    scanf("%d%d",&m,&n);
    s[0]=0;
    memset(b,0,sizeof(b));
    memset(ans,0,sizeof(ans));
    for(int i=1; i<=m; i++)
    {
        scanf("%d",&a[i]);
        if(a[i]<=m) b[a[i]]++;
    }
    for(int i=1; i<=n; i++)
        scanf("%d%d",&l[i],&r[i]);

    for(int i=1; i<=m; i++)
        if(i<=b[i])
        {
            for(int j=1; j<=m; j++)
                s[j]=s[j-1]+(a[j]==i);
            for(int j=1;j<=n;j++)
            if(s[r[j]]-s[l[j]-1]==i) ans[j]++;
        }
   for(int i=1;i<=n;i++)
    printf("%d\n",ans[i]);
    return 0;
}

codeforces 221D Little Elephant and Array,布布扣,bubuko.com

codeforces 221D Little Elephant and Array

原文：http://blog.csdn.net/knight_kaka/article/details/21643319