B. 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 numbersalj, 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
7 2 3 1 2 2 3 3 7 1 7 3 4
output
3 1
main thing is that we cant use map for the hashing so but if any array val > size of array than it will never contribute in the answer ( since cant ocure that times ) so just discard it ..
This problem can be solve in simpler O(NsqrtN) solution, but I will describe O(NlogN) one.
We will solve this problem in offline. For each x (0 ≤ x < n) we should keep all the queries that end in x. Iterate that x from 0 to n - 1. Also we need to keep some array D such that for current x Dl + Dl + 1 + ... + Dx will be the answer for query [l;x]. To keep D correct, before the processing all queries that end in x, we need to update D. Let t be the current integer in A, i. e. Ax, and vector P be the list of indices of previous occurences of t (0-based numeration of vector). Then, if |P| ≥ t, you need to add 1 to DP[|P| - t], because this position is now the first (from right) that contains exactly t occurences of t. After that, if |P| > t, you need to subtract 2 from DP[|P| - t - 1], in order to close current interval and cancel previous. Finally, if |P| > t + 1, then you need additionally add 1 to DP[|P| - t - 2] to cancel previous close of the interval.
----------------------------------------------CODE-----------------------------------------------------------------------------
#include<bits/stdc++.h>
typedef long long int lli;
using namespace std;
int ans=0;
int ch[1000000];
int n;
struct node
{
int x,y,index;
} qry[1000000];
int bck_sz=441;
int result[1000000];
int has[1000000];
int arr[10000000];
int read_int(){
char r;
bool start=false,neg=false;
int ret=0;
while(true){
r=getchar();
if((r-'0'<0 || r-'0'>9) && r!='-' && !start){
continue;
}
if((r-'0'<0 || r-'0'>9) && r!='-' && start){
break;
}
if(start)ret*=10;
start=true;
if(r=='-')neg=true;
else ret+=r-'0';
}
if(!neg)
return ret;
else
return -ret;
}
bool compare(node a,node b)
{
int i,j;
i=a.x/bck_sz;
j=b.x/bck_sz;
if(i==j)
{
if(a.y<b.y)
return 1;
else
return 0;
}
else{
if(i<j)
return 1;
else
return 0;
}
}
int join(int num)
{
//cout<<" add "<<num<<endl;
if(num>n) return 0;
has[num]++;
if(has[num]==num)
{
ans++;
// cout<<" inc "<<endl;
}
else if(has[num]==num+1) ans-=1;
}
int del(int num)
{
if(num>n) return 0;
if(has[num]==num) ans--;
has[num]--;
if(has[num]==num) ans++;
}
int main()
{
n=read_int();
int q;
q=read_int();
for(int i=0;i<n;i++)
arr[i]=read_int();
for(int i=0;i<q;i++)
{
int a,b;
a=read_int();
b=read_int();
a-=1;
b-=1;
qry[i].x=a;
qry[i].y=b;
qry[i].index=i;
}
sort(qry,qry+q,compare);
int l=0,r=-1;
for(int i=0;i<q;i++)
{
int x=qry[i].x;
int y=qry[i].y;
int index=qry[i].index;
// cout<<" qidx "<<index<<endl;
while(r<y)
{
r++;
join(arr[r]);
}
while(l>x)
{
l--;
join(arr[l]);
}
while(l<x)
{
del(arr[l]);
l++;
}
while(r>y)
{
del(arr[r]);
r--;
}
// cout<<ans<<endl;
result[index]=ans;
}
for(int i=0;i<q;i++)
{
printf("%d ",result[i]);
}
}
