题意
简化题意：
给定长度为(n)的初始值都为(0)的序列，有(m)次操作，求(m)次操作过后的整个序列
每次操作如下：
(1.)对区间([l,r])中的所有元素与(h)取(max)
(2.)对区间([l,r])中的所有元素与(h)取(min)
分析
线段树好题
一道 区修 单查 可离线 的题目
首先我们要明确这道题(2e6)的数据大概率就是要用线段树在(O(nlogn))时间范围内解决
然后我们现在的问题就在于要维护哪些标记
首先，我们最后要询问的值是(val)，还是单点，所以我们可以知道这个维护的东西是什么都无所谓，只要能确定某个单点的值就行了
然后看到题目这个肯定跟区间的最大值和最小值有关，那么我们干脆就维护(Max)和(Min)标记吧~
(Max)和(Min)分别代表区间最大值和区间最小值
那么我们考虑标记如何下传，就是(pushdown)函数的写法
我们可以发现这样的一个事情（关于下传标记时的标记覆盖问题）
就是如果我们当前这个点的两个标记为(Max1)和(Min1)，那么假设我们现在要从这个点的父亲结点下传一个(Min2)标记：
[Max1=min{(Max1,Min2)}\
Min1=min{(Min1,Min2)}
]
然后(Max2)标记也同理：
[Max1=max{(Max1,Max2)}\
Min1=max{(Min1,Max2)}
]
这样我们就解决了(pushdown)函数的问题啦~
那么代码也不难得出，其他具体的细节也在代码里看吧
代码
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=2e6+5;
int n,m,op;
int maxn[N<<2],minn[N<<2];
void pushdown(int x){
maxn[x<<1]=max(maxn[x<<1],maxn[x]);
minn[x<<1]=max(minn[x<<1],maxn[x]);
maxn[x<<1|1]=max(maxn[x<<1|1],maxn[x]);
minn[x<<1|1]=max(minn[x<<1|1],maxn[x]);
maxn[x<<1]=min(maxn[x<<1],minn[x]);
minn[x<<1]=min(minn[x<<1],minn[x]);
maxn[x<<1|1]=min(maxn[x<<1|1],minn[x]);
minn[x<<1|1]=min(minn[x<<1|1],minn[x]);
maxn[x]=0,minn[x]=0x3f3f3f3f;
return ;
}
void modify1(int x,int l,int r,int ql,int qr,int val){
if(ql<=l&&qr>=r){
maxn[x]=max(maxn[x],val);
minn[x]=max(minn[x],val);
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(ql<=mid) modify1(x<<1,l,mid,ql,qr,val);
if(qr>mid) modify1(x<<1|1,mid+1,r,ql,qr,val);
return ;
}
void modify2(int x,int l,int r,int ql,int qr,int val){
if(ql<=l&&qr>=r){
maxn[x]=min(maxn[x],val);
minn[x]=min(minn[x],val);
return ;
}
pushdown(x);
int mid=(l+r)>>1;
if(ql<=mid) modify2(x<<1,l,mid,ql,qr,val);
if(qr>mid) modify2(x<<1|1,mid+1,r,ql,qr,val);
return ;
}
int query(int x,int l,int r,int ql,int qr){
if(l==r) return maxn[x];
pushdown(x);
int mid=(l+r)>>1;
if(ql<=mid) return query(x<<1,l,mid,ql,qr);
else if(qr>mid) return query(x<<1|1,mid+1,r,ql,qr);
return 0;
}
int main(){
read(n),read(m);
for(int i=1;i<=(n<<2);i++) maxn[i]=0,minn[i]=0x3f3f3f3f;
while(m--){
read(op);
int l,r,h;
read(l),read(r),read(h);
l++,r++;
if(op==1) modify1(1,1,n,l,r,h);
else modify2(1,1,n,l,r,h);
}
for(int i=1;i<=n;i++) write(query(1,1,n,i,i)),putchar('
');
return 0;
}