codeforces 220 B. Little Elephant and Array

2016-02-13 · 2 min read · 分块莫队算法

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

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

思路：首先，a[i]很大。。。但是n最大才1e5...每个a[i]最多出现1E5次。。所以对于大于1E5的a[i]对答案没有贡献。其次，上莫队算法。

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

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair

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

1int n,m;
2int a[N];
3int pos[N];
4int sum;
5int ans[N];
6int cnt[N];

1struct node
2{
3    int l,r;
4    int id;

1    bool operator<(node b)const
2    {
3	if (pos[l]==pos[b.l]) return r<b.r;
4	return pos[l]<pos[b.l];
5    }
6}q[N];

void update( int x,int d)
{

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

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

1}
2int main()
3{
4	#ifndef  ONLINE_JUDGE 
5	freopen("code/in.txt","r",stdin);
6  #endif

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

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

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

1	    if (r<pr)
2	    {
3		for ( int j = r+1 ; j <= pr ; j++) update(j,-1);
4	    }
5	    else
6	    {
7		for ( int j = pr +1 ; j <= r ; j++) update(j,1);
8	    }

	    pr = r;

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

1	    if (l<pl)
2	    {
3		for ( int j = l ; j <= pl-1 ; j++) update(j,1);
4	    }
5	    else
6	    {
7		for ( int j = pl ; j <= l-1 ; j++) update(j,-1);
8	    }

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

	//    cout<<endl;
	}

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

1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}