题目描述
给定一个长度为 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
",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;
}