CodeForces 221D Little Elephant and Array

Little Elephant and Array

The Little Elephant loves playing with arrays. He has array a, consisting of n positive integers, indexed from 1 to n. Let’s denote the number with index i as ai.

Additionally the Little Elephant has m queries to the array, each query is characterised by a pair of integers lj and rj (1 ≤ lj ≤ rj ≤ n). For each query lj, rj the Little Elephant has to count, how many numbers x exist, such that number x occurs exactly x times among numbers alj, alj + 1, …, arj.

Help the Little Elephant to count the answers to all queries.

Input
The first line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the size of array a and the number of queries to it. The next line contains n space-separated positive integers a1, a2, …, an (1 ≤ ai ≤ 109). Next m lines contain descriptions of queries, one per line. The j-th of these lines contains the description of the j-th query as two space-separated integers lj and rj (1 ≤ lj ≤ rj ≤ n).

Output
In m lines print m integers — the answers to the queries. The j-th line should contain the answer to the j-th query.

Sample test(s)
input
7 2
3 1 2 2 3 3 7
1 7
3 4
output
3
1

题目大意
给定一个长度为n的数组，进行m次询问。每一次询问给出两个数l和r，表示在数组区间【l,r】内查询有多少数x使得x本身等于区间内x的个数。
一次性输出查询结果。

#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);//扫的时候用s数组记录该值在每个位置及之前出现的次数，然后在逐一对每个区间进行判断就行了。
            for(int j=1;j<=n;j++)
            if(s[r[j]]-s[l[j]-1]==i) ans[j]++; //前缀和公式sum(l,r)=s[r]-s[l-1];
        }
   for(int i=1;i<=n;i++)
    printf("%d\n",ans[i]);
    return 0;
}

注：
if(i<=b[i])可能会比较难理解
i为数自身的值吧b[i]为i出现的次数
如果满足计数条件的话必须要满足 “出现的次数>=值” 即 i<=b[i]
我试了一下改成>=在codeforces上也能过可能测试数据比较极限？
其实原数据稍微改一下就好理解了
Sample test(s)
input
7 2
3 1 2 2 3 3 3
1 7
5 7
output（正确）
3
1
而如果改成>=
输出会是
output（错误）
0
1