# codeforces 220 B. Little Elephant and Array

Posted by 111qqz on Saturday, February 13, 2016

## TOC

http://codeforces.com/contest/220/problem/B

## 题意：n个数，m个查询区间，对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。

``````/* ***********************************************
Author :111qqz
Created Time :2016年02月14日 星期日 00时47分18秒
File Name :code/cf/problem/220B.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;

int n,m;
int a[N];
int pos[N];
int sum;
int ans[N];
int cnt[N];

struct node
{
int l,r;
int id;

bool operator<(node b)const
{
if (pos[l]==pos[b.l]) return r<b.r;
return pos[l]<pos[b.l];
}
}q[N];

void update( int x,int d)
{

if (a[x]>100000) return;
if (cnt[a[x]]==a[x]) sum--;
cnt[a[x]]+=d;
if (cnt[a[x]]==a[x]) sum++;

//  cout<<"x:"<<x<<" d:"<<d<<" sum:"<<sum<<endl;

}
int main()
{
#ifndef  ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif

cin>>n>>m;
ms(pos,-1);
ms(cnt,0);
int siz = int(sqrt(n));
for ( int i = 1 ; i <= n ; i++)
{
scanf("%d",&a[i]);
pos[i] = (i-1)/siz;
}

for ( int i = 1 ;i  <= m ; i++)
{
scanf("%d %d",&q[i].l,&q[i].r);
q[i].id = i ;
}
sort(q+1,q+m+1);

//	for ( int i = 1 ;i  <= m ; i++) cout<<q[i].l<<" "<<q[i].r<<endl;
int pl = 1;
int pr = 0;
int id,l,r;
sum = 0 ; //不小心又定义了个局部变量2333
for ( int i = 1 ; i <= m ; i++)
{
id = q[i].id;
l = q[i].l;
r = q[i].r;

if (r<pr)
{
for ( int j = r+1 ; j <= pr ; j++) update(j,-1);
}
else
{
for ( int j = pr +1 ; j <= r ; j++) update(j,1);
}

pr = r;

//   cout<<"sum1:"<<sum<<endl;

if (l<pl)
{
for ( int j = l ; j <= pl-1 ; j++) update(j,1);
}
else
{
for ( int j = pl ; j <= l-1 ; j++) update(j,-1);
}

pl = l;
//	    cout<<"sum2:"<<sum<<endl;
ans[id] = sum;

//    cout<<endl;
}

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

#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
``````

「真诚赞赏，手留余香」