本文主要是介绍P4560 [IOI2014] Wall 砖墙，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
*原题链接*
做法：线段树
一道比较基础的线段树练手题，区间赋值，在修改时加些判断剪枝。
对于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){//Addif(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){//Removeif(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;
}这篇关于P4560 [IOI2014] Wall 砖墙的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
