线段树--luoguP4560 [IOI2014]Wall 砖墙

本文主要是介绍线段树--luoguP4560 [IOI2014]Wall 砖墙，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
很巧啊只需要维护上界和下界就好了
一开始以为要维护四个，其实只用维护两个就好了，如果到了 $l = r$ 的时候修改一下序列上的值就行。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 2000005
#define ls cur<<1
#define rs cur<<1|1
using namespace std;inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f;
}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}int n,m,mn[N<<2],mx[N<<2],ans[N];inline void pushdown(int cur,int l,int r){if(l==r){if(mn[cur]!=-1) ans[l]=min(ans[l],mn[cur]);if(mx[cur]!=-1) ans[l]=max(ans[l],mx[cur]);return;}if(mn[cur]!=-1){if(mn[ls]!=-1) mn[ls]=min(mn[ls],mn[cur]);else mn[ls]=mn[cur];mx[ls]=min(mx[ls],mn[cur]);if(mn[rs]!=-1) mn[rs]=min(mn[rs],mn[cur]);else mn[rs]=mn[cur];mx[rs]=min(mx[rs],mn[cur]);mn[cur]=-1;}if(mx[cur]!=-1){mx[ls]=max(mx[ls],mx[cur]); mx[rs]=max(mx[rs],mx[cur]);if(mn[ls]!=-1) mn[ls]=max(mn[ls],mx[cur]);if(mn[rs]!=-1) mn[rs]=max(mn[rs],mx[cur]);mx[cur]=-1;}
}void update(int cur,int L,int R,int ql,int qr,int tp,int h){if(L<=ql && qr<=R){if(tp==1){mx[cur]=max(mx[cur],h);if(mn[cur]!=-1) mn[cur]=max(mn[cur],h);}else{if(mn[cur]==-1) mn[cur]=h;else mn[cur]=min(mn[cur],h);if(mx[cur]!=-1) mx[cur]=min(mx[cur],h);}if(ql==qr){if(mn[cur]!=-1) ans[ql]=min(ans[ql],mn[cur]);if(mx[cur]!=-1) ans[ql]=max(ans[ql],mx[cur]);} return;}int mid=(ql+qr)>>1; pushdown(cur,ql,qr);if(L<=mid) update(ls,L,R,ql,mid,tp,h);if(mid<R) update(rs,L,R,mid+1,qr,tp,h);
}void query(int cur,int ql,int qr){pushdown(cur,ql,qr);if(ql==qr) {printf("%d\n",ans[ql]);return;}int mid=(ql+qr)>>1;query(ls,ql,mid); query(rs,mid+1,qr);
}int main(){n=rd(); m=rd(); memset(mn,-1,sizeof mn); memset(mx,-1,sizeof mx);int t,l,r,h;while(m--){t=rd(); l=rd(); r=rd(); h=rd(); ++l,++r;update(1,l,r,1,n,t,h);}query(1,1,n);return 0;
}