[bzoj3339]Rmq Problem||[bzoj3585]mex

Rmq Problem bzoj-3339||mex bzoj-3585

题目大意：给定一个长度为n的数列a，多次讯问区间l,r中最小的不属于集合{$A_l,A_{l+1}...A_r$}的非负整数。

注释：n,q$\le$200,000 ; 0$\le A_i \le$200,000 ; $A_i$均为非负整数，1<=l<=r<=n，l和r均为正整数。

想法：网上很多其他的算法(suika：离线+莫队，WinnieChen：在线权值线段树)，我们来聊一聊离线加线段树。

　　首先，我们将询问离线，按左端点为第一关键字排序。

　　紧接着，预处理一点东西：暴力求出1~i之间的答案，以及每一个数位置pos的数a[pos]右边第一个等于a[pos]的数，它的位置我们记为nxt[pos]。

　　然后，我们从左往右扫，对于当前数a[l]，对于l+1到nxt[l]-1之间的数都需要进行区间赋值乘a[l]，这个操作我们用线段树完成。如果当前节点还是一个被查询区间的左端点的话，我们直接输出右端点对应的mex即可。

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <algorithm>

#define lson pos<<1

#define rson pos<<1|1

#define inf 0x7fffffff

using namespace std;

int n,m,k=0;

int a[200005],sg[200005],ans[200005],next[200005],last[200005];

int ls[600005],rs[600005],mn[600005];

bool mark[200001];

struct data{int l,r,id;}q[200005];

bool cmp(data a,data b)

{return a.l<b.l;}

void build(int l,int r,int pos)

{

	ls[pos]=l;

	rs[pos]=r;

	mn[pos]=inf;

	if(l==r)

	{

		mn[pos]=sg[l];

		return;

	}

	int mid=(l+r)>>1;

	build(l,mid,lson);build(mid+1,r,rson);

}

void pushdown(int pos)

{

	int l=ls[pos],r=rs[pos];

	if(l==r)return;

	mn[lson]=min(mn[pos],mn[lson]);

	mn[rson]=min(mn[pos],mn[rson]);

}

int ask(int pos,int x)

{

	if(mn[pos]!=inf)pushdown(pos);

	int l=ls[pos],r=rs[pos];

	if(l==r)return mn[pos];

	int mid=(l+r)>>1;

	if(x<=mid)return ask(lson,x);

	return ask(rson,x);

}

void update(int pos,int x,int y,int val)

{

	if(mn[pos]!=inf)pushdown(pos);

	int l=ls[pos],r=rs[pos];

	if(l==x&&y==r){mn[pos]=min(mn[pos],val);return;}

	int mid=(l+r)>>1;

	if(y<=mid)update(lson,x,y,val);

	else if(x>mid)update(rson,x,y,val);

	else

	{

		update(lson,x,mid,val);

		update(rson,mid+1,y,val);

	}

}

int main()

{

	scanf("%d%d",&n,&m);

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

	{

		scanf("%d",&a[i]);

	}

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

	{

		mark[a[i]]=1;

		if(a[i]==k)

			while(mark[k])k++;

		sg[i]=k;

	}

	build(1,n,1);

	for(int i=n;i>0;i--)

		next[i]=last[a[i]],last[a[i]]=i;

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

	{

		scanf("%d%d",&q[i].l,&q[i].r);

		q[i].id=i;

	}

	sort(q+1,q+m+1,cmp);

	int now=1;

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

	{

		while(now<q[i].l)

		{

			if(!next[now])next[now]=n+1;

			update(1,now,next[now]-1,a[now]);

			now++;

		}

		ans[q[i].id]=ask(1,q[i].r);

	}

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

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

	return 0;

}

小结：对着hzwer学长写的动态开点，感觉爆炸。注意pushdown的时候要记得删除之前的标记。

巴特西

[bzoj3339]Rmq Problem||[bzoj3585]mex_线段树

最新文章

热门文章