BZOJ_3585_mex && BZOJ_3339_Rmq Problem_莫队+分块

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

Sample Output

1
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]);
}