【BZOJ3339&&3585】mex [莫队][分块]

mex

Time Limit: 20 Sec Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

　　有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Input

　　第一行n,m。
　　第二行为n个数。
　　从第三行开始，每行一个询问l,r。

Output

　　一行一个数，表示每个询问的答案。

Sample Input

　　5 5
　　2 1 0 2 1
　　3 3
　　2 3
　　2 4
　　1 2
　　3 5

Sample Output

　　1
　　2
　　3
　　0
　　3

HINT

　　1<=n,m<=200000, 0<=ai<=1e9

Solution

　　首先，权值>n的显然是没有用的，最多排满1~n。然后我们直接使用莫队，对权值分块，查询的时候看一下这个块里面权值数是否满了，即可做到O(sqrt(n))的查询。

Code

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cmath>

 using namespace std;

 typedef long long s64;

 const int ONE = ;

 const int INF = ;

 int n,m,Q,num;

 int a[ONE],block[ONE];

 int Ans[ONE];

 int C[ONE],Bc[ONE];

 struct power

 {

         int id;

         int l,r;

 }oper[ONE];

 int cmp(const power &a,const power &b)

 {

         if(block[a.l] != block[b.l]) return block[a.l] < block[b.l];

         return a.r < b.r;

 }

 int get()

 {

         int res=,Q=;  char c;

         while( (c=getchar())< || c>)

         if(c=='-')Q=-;

         if(Q) res=c-;

         while((c=getchar())>= && c<=)

         res=res*+c-;

         return res*Q;

 }

 void increa(int x) {if(x>n) return; C[x]++; if(C[x]==) Bc[block[x]]++;}

 void reduce(int x) {if(x>n) return; C[x]--; if(C[x]==) Bc[block[x]]--;}

 int Query()

 {

         int pos = ;

         for(int i=;i<=num;i++)

             if(Bc[i] < Q) {pos = i; break;}

         for(int i=(pos-)*Q+;i<=n+;i++)

             if(!C[i])

                 return i-;

 }

 int main()

 {

         n=get();    m=get();

         Q = sqrt(n);    num = (n-)/Q+;

         for(int i=;i<=n;i++)

             a[i] = get()+, block[i] = (i-)/Q+;

         for(int i=;i<=m;i++)

         {

             oper[i].id = i;

             oper[i].l = get();    oper[i].r = get();

         }

         sort(oper+, oper+m+, cmp);

         int l = , r = ;

         for(int i=;i<=m;i++)

         {

             while(r < oper[i].r) increa(a[++r]);

             while(oper[i].l < l) increa(a[--l]);

             while(r > oper[i].r) reduce(a[r--]);

             while(oper[i].l > l) reduce(a[l++]);

             Ans[oper[i].id] = Query();

         }

         for(int i=;i<=m;i++)

             printf("%d\n", Ans[i]);

 }

巴特西