*原题链接*
做法:线段树
一道比较基础的线段树练手题,区间赋值,在修改时加些判断剪枝。
对于add操作,如果此时区间里的最小值都大于等于h的话,就没必要操作,如果最大值都小于h的话,就直接区间赋值为h。对于remove操作同理。
时间复杂度大致为,实际会比这个要大一些。
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10,INF=0x3f3f3f3f;
int n,k;
struct node{
int l,r;
int mn,mx,tag;
}tr[N*4];
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-1') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
void pushdown(int u){
if(tr[u].tag==INF) return;
tr[u<<1].mn=tr[u<<1].mx=tr[u<<1].tag=tr[u].tag;
tr[u<<1|1].mn=tr[u<<1|1].mx=tr[u<<1|1].tag=tr[u].tag;
tr[u].tag=INF;
}
void pushup(int u){
tr[u].mn=min(tr[u<<1].mn,tr[u<<1|1].mn);
tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);
}
void build(int u,int l,int r){
if(l==r) tr[u]={l,r,0,0,INF};
else{
tr[u].l=l,tr[u].r=r;
int mid=(l+r)>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
}
void modify1(int u,int l,int r,int x){//Add
if(tr[u].l>=l&&tr[u].r<=r){
if(tr[u].mn>=x) return;
if(tr[u].mx<=x){
tr[u].mn=tr[u].mx=tr[u].tag=x;
return;
}
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify1(u<<1,l,r,x);
if(r>mid) modify1(u<<1|1,l,r,x);
pushup(u);
}
void modify2(int u,int l,int r,int x){//Remove
if(tr[u].l>=l&&tr[u].r<=r){
if(tr[u].mx<=x) return;
if(tr[u].mn>=x){
tr[u].mn=tr[u].mx=tr[u].tag=x;
return;
}
}
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(l<=mid) modify2(u<<1,l,r,x);
if(r>mid) modify2(u<<1|1,l,r,x);
pushup(u);
}
int query(int u,int x){
if(tr[u].l==x&&tr[u].r==x) return tr[u].mx;
pushdown(u);
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) return query(u<<1,x);
return query(u<<1|1,x);
}
int main(){
n=read(),k=read();
build(1,1,n);
while(k--){
int opt=read(),l=read(),r=read(),h=read();
l++,r++;
if(opt==1) modify1(1,l,r,h);
else modify2(1,l,r,h);
}
for(int i=1;i<=n;i++) cout<<query(1,i)<<endl;
return 0;
}