BZOJ_3585_mex && BZOJ_3339_Rmq Problem_莫队+分块
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
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
Sample Output
1
2
3
0
3
2
3
0
3
HINT
数据规模和约定
对于100%的数据：
1<=n,m<=200000
0<=ai<=109
1<=l<=r<=n
对于30%的数据：
1<=n,m<=1000
我的做法比较$sb$ 也比较裸，只能处理离线不修改的。
询问莫队，把权值分块，找到第一个不满的块，暴力查即可。
好像主席树也能做。
主席树链接http://www.cnblogs.com/suika/p/9062412.html
代码(3585&&3339)：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd() {
register int x=0;
register char s=nc();
while(s<'0'||s>'9')s=nc();
while(s>='0'&&s<='9')x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
#define N 200050
int pos[N],L[N],R[N],size,block,n,c[N],ans[N],h[N],ansblo[N],m;
struct A {
int l,r,id;
}q[N];
bool cmp(const A &x,const A &y) {
if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];
return x.r<y.r;
}
void del(int x) {
h[x]--;
if(h[x]==0) ansblo[pos[x]]--;
}
void add(int x) {
h[x]++;
if(h[x]==1) ansblo[pos[x]]++;
}
int query() {
int i,j;
for(i=1;i<=block;i++) {
if(ansblo[i]<R[i]-L[i]+1) {
for(j=L[i];j<=R[i];j++) {
if(!h[j]) return j;
}
}
}
return n;
}
void solve() {
int i,l=1,r=0;
for(i=1;i<=m;i++) {
while(l<q[i].l) del(c[l]),l++;
while(r>q[i].r) del(c[r]),r--;
while(l>q[i].l) l--,add(c[l]);
while(r<q[i].r) r++,add(c[r]);
ans[q[i].id]=query();
}
}
int main() {
n=rd(); m=rd();
int i,j;
size=sqrt(n); block=n/size;
for(i=1;i<=block;i++) {
L[i]=R[i-1]+1; R[i]=size*i;
for(j=L[i];j<=R[i];j++) {
c[j]=rd(); c[j]=min(c[j],n); pos[j]=i;
}
}
if(R[block]!=n) {
block++; L[block]=R[block-1]+1; R[block]=n;
for(i=L[block];i<=n;i++) {
c[i]=rd(); c[i]=min(c[i],n); pos[i]=block;
}
}
for(i=1;i<=m;i++) {
q[i].l=rd(); q[i].r=rd(); q[i].id=i;
}
L[1]=0; pos[0]=1;
sort(q+1,q+m+1,cmp);
solve();
for(i=1;i<=m;i++) printf("%d\n",ans[i]);
}