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
