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)的快速转移，所以可以用莫队算法。刚接触不是太懂，等以后更加了解再更。

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 const int maxm=;

 int n,m,unit;

 struct Query{

     int l,r,id;

 }node[maxm];

 int a[maxn],b[maxn],c[maxn],num[maxn],ans[maxm];

 bool cmp(Query a,Query b) {

     if(a.l/unit!=b.l/unit) return a.l/unit<b.l/unit;

     else return a.r<b.r;

 }

 int main() {

     scanf("%d%d",&n,&m);

     unit=(int)sqrt(n*1.0);

     for(int i=;i<=n;i++) {

         scanf("%d",&a[i]);

         b[i]=a[i];

     }

     sort(b+,b++n);

     for(int i=;i<=n;i++) {

         c[i]=lower_bound(b+,b++n,a[i])-b;

     }

     for(int i=;i<=m;i++) {

         node[i].id=i;

         scanf("%d%d",&node[i].l,&node[i].r);

     }

     sort(node+,node+m+,cmp);

     int l=,r=,temp=;

     for(int i=;i<=m;i++) {

         while(r<node[i].r) { //右扩

             r++;

             if(num[c[r]]+==a[r]) temp++;

             else if(num[c[r]]==a[r]) temp--;

             num[c[r]]++;

         }

         while(r>node[i].r) { //右缩

             if(num[c[r]]==a[r]) temp--;

             else if(num[c[r]]-==a[r]) temp++;

             num[c[r]]--;

             r--;

         }

         while(l>node[i].l) { //左扩

             l--;

             if(num[c[l]]+==a[l]) temp++;

             else if(num[c[l]]==a[l]) temp--;

             num[c[l]]++;

         }

         while(l<node[i].l) {  //左缩

             if(num[c[l]]==a[l]) temp--;

             else if(num[c[l]]-==a[l]) temp++;

             num[c[l]]--;

             l++;

         }

         ans[node[i].id]=temp;

     }

     for(int i=;i<=m;i++) printf("%d\n",ans[i]);

 }

巴特西

Codeforces 220B

最新文章

热门文章