codeforces - B. Little Elephant and Array

B. Little Elephant and Array

time limit per test4 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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
inputCopy
7 2
3 1 2 2 3 3 7
1 7
3 4
outputCopy
3
1

一道裸的莫队，我们记录每个数字出现的次数，然后看是否更新答案即可。只不过数字比较大，要hash一下。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,m,cl=1,cr,bl,a[N],res[N],s;
unordered_map<int,int> cnt;
struct node{
	int l,r,id;
}t[N];
int cmp(const node &s1,const node &s2){
	return (s1.l/bl==s2.l/bl)?(s1.r<s2.r):(s1.l<s2.l);
}
inline void add(int x){
	++cnt[a[x]];	s+=(cnt[a[x]]==a[x]);	s-=(cnt[a[x]]==a[x]+1);
}
inline void del(int x){
	--cnt[a[x]];	s+=(cnt[a[x]]==a[x]);	s-=(cnt[a[x]]+1==a[x]);
}
signed main(){
	scanf("%d %d",&n,&m);	bl=sqrt(n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(int i=1;i<=m;i++)	scanf("%d %d",&t[i].l,&t[i].r),t[i].id=i;
	sort(t+1,t+1+m,cmp);
	for(int i=1;i<=m;i++){
		int L=t[i].l;	int R=t[i].r; 
		while(cr<R)	add(++cr);
		while(cl>L)	add(--cl);
		while(cr>R)	del(cr--);
		while(cl<L)	del(cl++);
		res[t[i].id]=s;
	}
	for(int i=1;i<=m;i++)	printf("%d\n",res[i]);
	return 0;
}