P4560 [IOI2014]Wall 砖墙

题目描述

给定一个长度为 nn且初始值全为 00的序列。你需要支持以下两种操作：

Add L, R, hL,R,h：将序列 [L, R][L,R]内所有值小于 hh的元素都赋为 hh，此时不改变高度大于 hh的元素值
Remove L, R, hL,R,h：将序列 [L, R][L,R]内所有值大于 hh的元素都赋为 hh，此时不改变高度小于 hh的元素值

你需要输出进行 kk次上述操作之后的序列。

解析

显然每次操作会对一段区间的取值范围造成影响，那么不妨我们维护区间取值的上下界，就可以轻松A掉这题。

最简单的方法就是线段树（不过貌似有人高级数据结构T了233）

那么维护上下界实质上也就是维护区间最大最小值，所以我们每次打个lazytag以保留操作对区间的影响就行了。注意是打标记而不是维护信息，我们不用区间查询，维护了这堆信息也没用，还浪费时间。。。

最后输出我们把lazytag造成的所有影响很好的维护出来，再遍历一次整棵线段树输出叶子节点的lazytag就行了。

那如何维护lazytag呢？我们就要关注pushdown怎么弄。

设\(up(h),down(h)\)分别对应在线段树上进行Add，Remove两种操作，改变的高度为\(h\)。

对于\(up(h)\)，设改变的区间上下界为\(u,d\)：

若\(x<d\)，不会对区间造成影响
若\(d<x<u\)，此时\(d\)变为\(x\)，\(u\)不变
若\(x>u\)，此时\(d,u\)都变为\(x\)。

参考代码

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#define INF 0x3f3f3f3f

#define N 2000010

using namespace std;

inline int read()

{

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

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

struct node{

	int l,r;

	int up,down;

}t[N<<2];

int n,k;

inline void pushdown(int p)

{

	if(p==0) return;

	if(t[p].up!=0){

		t[p<<1].up=max(t[p].up,t[p<<1].up);

		t[p<<1|1].up=max(t[p].up,t[p<<1|1].up);

		if(t[p<<1].down<t[p].up) t[p<<1].down=t[p].up;

		if(t[p<<1|1].down<t[p].up) t[p<<1|1].down=t[p].up;

		t[p].up=0;

	}

	if(t[p].down!=INF){

		t[p<<1].down=min(t[p].down,t[p<<1].down);

		t[p<<1|1].down=min(t[p].down,t[p<<1|1].down);

		if(t[p<<1].up>t[p].down) t[p<<1].up=t[p].down;

		if(t[p<<1|1].up>t[p].down) t[p<<1|1].up=t[p].down;

		t[p].down=INF;

	}

}

inline void build(int p,int l,int r)

{

	t[p].l=l,t[p].r=r;t[p].up=0,t[p].down=INF;

	if(l==r) return;

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

	build(p<<1,l,mid);

	build(p<<1|1,mid+1,r);

}

inline void up(int p,int l,int r,int val)

{

	if(l<=t[p].l&&t[p].r<=r){

		t[p].up=max(t[p].up,val);

		t[p].down=max(val,t[p].down);

		return;

	}

	pushdown(p);

	int mid=(t[p].l+t[p].r)>>1;

	if(l<=mid) up(p<<1,l,r,val);

	if(r>mid) up(p<<1|1,l,r,val);

}

inline void down(int p,int l,int r,int val)

{

	if(l<=t[p].l&&t[p].r<=r){

		t[p].down=min(t[p].down,val);

		t[p].up=min(t[p].up,val);

		return;

	}

	pushdown(p);

	int mid=(t[p].l+t[p].r)>>1;

	if(l<=mid) down(p<<1,l,r,val);

	if(r>mid) down(p<<1|1,l,r,val);

}

inline void query(int p,int l,int r)

{

	if(t[p].l==t[p].r){

		printf("%d\n",t[p].up);

		return;

	}

	pushdown(p);

	int mid=(t[p].l+t[p].r)>>1;

	if(l<=mid) query(p<<1,l,r);

	if(r>mid) query(p<<1|1,l,r);

}

int main()

{

	n=read(),k=read();

	build(1,1,n);

	for(int i=1;i<=k;++i){

		int cmd=read(),l=read(),r=read(),val=read();

		++l,++r;

		if(cmd==1) up(1,l,r,val);

		else down(1,l,r,val);

	}

	query(1,1,n);

	return 0;

}

巴特西

P4560 [IOI2014]Wall 砖墙

题目描述

解析

参考代码

最新文章

热门文章