LUOGU P4560 [IOI2014]Wall 砖墙 (线段树)

解题思路

　　线段树打标记，刚开始想复杂了，维护了四个标记。后来才知道只需要维护一个最大值最小值即可，然后更新的时候分类讨论一下。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

using namespace std;

const int MAXN = 2000005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int n,a[MAXN],high[MAXN<<2],low[MAXN<<2],m;

inline int min(int x,int y){

	return x<y?x:y;

}

inline int max(int x,int y){

	return x>y?x:y;

}

inline void pushdown(int x,int l,int r){

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

	if(l==r) {

		if(low[x]!=-1) a[l]=min(a[l],low[x]);

		if(high[x]!=-1) a[l]=max(a[l],high[x]);

		return ;

	}

	if(low[x]!=-1) {

		if(low[x<<1]!=-1) low[x<<1]=min(low[x<<1],low[x]);

		else low[x<<1]=low[x];

		if(high[x<<1]>low[x]) high[x<<1]=low[x];

		if(low[x<<1|1]!=-1) low[x<<1|1]=min(low[x<<1|1],low[x]);

		else low[x<<1|1]=low[x];

		if(high[x<<1|1]>low[x]) high[x<<1|1]=low[x];

		low[x]=-1;

	}

	if(high[x]!=-1){

		high[x<<1]=max(high[x<<1],high[x]);

		if(high[x]>low[x<<1] && low[x<<1]!=-1) low[x<<1]=high[x];

		high[x<<1|1]=max(high[x<<1|1],high[x]);

		if(high[x]>low[x<<1|1] && low[x<<1|1]!=-1) low[x<<1|1]=high[x];

		high[x]=-1;

	}

}

void update_h(int x,int l,int r,int L,int R,int k){

	if(L<=l && r<=R) {

		high[x]=max(high[x],k);

		if(low[x]!=-1 && low[x]<k) low[x]=k;

		if(l==r) {

			if(low[x]!=-1) a[l]=min(a[l],low[x]);

			if(high[x]!=-1) a[l]=max(a[l],high[x]);

		}

		return ;

	}

	int mid=(l+r)>>1;pushdown(x,l,r);

	if(L<=mid) update_h(x<<1,l,mid,L,R,k);

	if(mid<R)  update_h(x<<1|1,mid+1,r,L,R,k);

}

void update_l(int x,int l,int r,int L,int R,int k){

	if(L<=l && r<=R) {

		if(low[x]==-1) low[x]=k;

		else low[x]=min(low[x],k);

		if(high[x]!=-1 && high[x]>k) high[x]=k;

		if(l==r){

			if(low[x]!=-1) a[l]=min(a[l],low[x]);

			if(high[x]!=-1) a[l]=max(a[l],high[x]);

		}

		return ;

	}

	int mid=(l+r)>>1;pushdown(x,l,r);

	if(L<=mid) update_l(x<<1,l,mid,L,R,k);

	if(mid<R) update_l(x<<1|1,mid+1,r,L,R,k);

}

void query(int x,int l,int r){

	if(l==r) {pushdown(x,l,r);printf("%d\n",a[l]);return ;}

	int mid=(l+r)>>1;pushdown(x,l,r);

	query(x<<1,l,mid);query(x<<1|1,mid+1,r);

}

int main(){

	memset(low,-1,sizeof(low));

	memset(high,-1,sizeof(high));

	n=rd(),m=rd();int op,l,r,k;

	while(m--){

		op=rd(),l=rd(),r=rd(),k=rd();l++;r++;

		if(op==1) update_h(1,1,n,l,r,k);

		else update_l(1,1,n,l,r,k);

	}

	query(1,1,n);

	return 0;

}

巴特西

LUOGU P4560 [IOI2014]Wall 砖墙 (线段树)

解题思路

代码

最新文章

热门文章