首页 > 其他 > 详细

BZOJ_3585_mex && BZOJ_3339_Rmq Problem_莫队+分块

时间:2018-04-20 15:08:44      阅读:172      评论:0      收藏:0      [点我收藏+]

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$ 也比较裸,只能处理离线不修改的。

询问莫队,把权值分块,找到第一个不满的块,暴力查即可。

好像主席树也能做,挖坑待填。

 

代码(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]);
}

 

BZOJ_3585_mex && BZOJ_3339_Rmq Problem_莫队+分块

原文:https://www.cnblogs.com/suika/p/8890783.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!