Codeforces 220B

B. Little Elephant and Array time limit per test 4 seconds memory limit per test 256 megabytes input standard input output standard output

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.

Examples input Copy

7 2
3 1 2 2 3 3 7
1 7
3 4

output Copy

3
1

题目大意：询问区间l,r间有几个数的出现次数等于数值本身。

由于题目满足由区间（l,r）-> (l,r+1)、(l,r-1)、(l-1，r)、(l+1,r)的快速转移，所以可以用莫队算法。刚接触不是太懂，等以后更加了解再更。

 1 #include
 2 using namespace std;
 3 
 4 const int maxn=100010;
 5 const int maxm=100010;
 6 int n,m,unit;
 7 struct Query{
 8     int l,r,id;
 9 }node[maxm];
10 
11 int a[maxn],b[maxn],c[maxn],num[maxn],ans[maxm];
12 
13 bool cmp(Query a,Query b) {
14     if(a.l/unit!=b.l/unit) return a.l/unitunit;
15     else return a.r<b.r;
16 }
17 
18 int main() {
19     scanf("%d%d",&n,&m);
20     unit=(int)sqrt(n*1.0);
21     for(int i=1;i<=n;i++) {
22         scanf("%d",&a[i]);
23         b[i]=a[i];
24     }
25     sort(b+1,b+1+n);
26     for(int i=1;i<=n;i++) {
27         c[i]=lower_bound(b+1,b+1+n,a[i])-b;
28     }
29     for(int i=1;i<=m;i++) {
30         node[i].id=i;
31         scanf("%d%d",&node[i].l,&node[i].r);
32     }
33     sort(node+1,node+m+1,cmp);
34     int l=1,r=0,temp=0;
35     for(int i=1;i<=m;i++) {
36         while(r//右扩
37             r++;
38             if(num[c[r]]+1==a[r]) temp++;
39             else if(num[c[r]]==a[r]) temp--;
40             num[c[r]]++;
41         }
42         while(r>node[i].r) { //右缩
43             if(num[c[r]]==a[r]) temp--;
44             else if(num[c[r]]-1==a[r]) temp++;
45             num[c[r]]--;
46             r--;
47         }
48         while(l>node[i].l) { //左扩
49             l--;
50             if(num[c[l]]+1==a[l]) temp++;
51             else if(num[c[l]]==a[l]) temp--;
52             num[c[l]]++;
53         }
54         while(l//左缩
55             if(num[c[l]]==a[l]) temp--;
56             else if(num[c[l]]-1==a[l]) temp++;
57             num[c[l]]--;
58             l++;
59         }
60         ans[node[i].id]=temp;
61     }
62     for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
63 }