codeforces 220 B. Little Elephant and Array
http://codeforces.com/contest/220/problem/B
题意：n个数，m个查询区间，对于每一个区间[l,r]输出区间中cnt[x]==x的数的个数。
思路：首先，a[i]很大。。。但是n最大才1e5…每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次，上莫队算法。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月14日 星期日 00时47分18秒
4File Name :code/cf/problem/220B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34
35int n,m;
36int a[N];
37int pos[N];
38int sum;
39int ans[N];
40int cnt[N];
41
42struct node
43{
44 int l,r;
45 int id;
46
47 bool operator<(node b)const
48 {
49 if (pos[l]==pos[b.l]) return r<b.r;
50 return pos[l]<pos[b.l];
51 }
52}q[N];
53
54
55void update( int x,int d)
56{
57
58 if (a[x]>100000) return;
59 if (cnt[a[x]]==a[x]) sum--;
60 cnt[a[x]]+=d;
61 if (cnt[a[x]]==a[x]) sum++;
62
63 // cout<<"x:"<<x<<" d:"<<d<<" sum:"<<sum<<endl;
64
65}
66int main()
67{
68 #ifndef ONLINE_JUDGE
69 freopen("code/in.txt","r",stdin);
70 #endif
71
72 cin>>n>>m;
73 ms(pos,-1);
74 ms(cnt,0);
75 int siz = int(sqrt(n));
76 for ( int i = 1 ; i <= n ; i++)
77 {
78 scanf("%d",&a[i]);
79 pos[i] = (i-1)/siz;
80 }
81
82 for ( int i = 1 ;i <= m ; i++)
83 {
84 scanf("%d %d",&q[i].l,&q[i].r);
85 q[i].id = i ;
86 }
87 sort(q+1,q+m+1);
88
89// for ( int i = 1 ;i <= m ; i++) cout<<q[i].l<<" "<<q[i].r<<endl;
90 int pl = 1;
91 int pr = 0;
92 int id,l,r;
93 sum = 0 ; //不小心又定义了个局部变量2333
94 for ( int i = 1 ; i <= m ; i++)
95 {
96 id = q[i].id;
97 l = q[i].l;
98 r = q[i].r;
99
100 if (r<pr)
101 {
102 for ( int j = r+1 ; j <= pr ; j++) update(j,-1);
103 }
104 else
105 {
106 for ( int j = pr +1 ; j <= r ; j++) update(j,1);
107 }
108
109 pr = r;
110
111 // cout<<"sum1:"<<sum<<endl;
112
113 if (l<pl)
114 {
115 for ( int j = l ; j <= pl-1 ; j++) update(j,1);
116 }
117 else
118 {
119 for ( int j = pl ; j <= l-1 ; j++) update(j,-1);
120 }
121
122 pl = l;
123// cout<<"sum2:"<<sum<<endl;
124 ans[id] = sum;
125
126 // cout<<endl;
127 }
128
129 for ( int i = 1 ; i <= m ;i ++) printf("%d\n",ans[i]);
130
131 #ifndef ONLINE_JUDGE
132 fclose(stdin);
133 #endif
134 return 0;
135}