线段树打标记的好（luo）题
打打标记，记得下移
= =听说2000000是用来卡线段树的
= =怎么办呢，，，
= =打个读入优化看看能不能卡过去吧
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int M=2000010; int n,m,i,opt,l,r,x; int mx1[M*4],mx2[M*4]; int read() { int x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } void pushdown(int p) { int l=p<<1,r=p<<1^1; if (mx2[p]>mx1[l])mx1[l]=mx2[l]=mx2[p]; else if (mx2[p]>mx2[l])mx2[l]=mx2[p]; if (mx2[p]>mx1[r])mx1[r]=mx2[r]=mx2[p]; else if (mx2[p]>mx2[r])mx2[r]=mx2[p]; if (mx1[p]<mx2[l])mx1[l]=mx2[l]=mx1[p]; else if (mx1[p]<mx1[l])mx1[l]=mx1[p]; if (mx1[p]<mx2[r])mx1[r]=mx2[r]=mx1[p]; else if (mx1[p]<mx1[r])mx1[r]=mx1[p]; } void pushup(int p) { int l=p<<1,r=p<<1^1; mx1[p]=max(mx1[l],mx1[r]); mx2[p]=min(mx2[l],mx2[r]); } void update1(int x,int y,int l,int r,int p,int t) { if (x==l&&y==r){ mx1[p]=max(mx1[p],t); mx2[p]=max(mx2[p],t); return; } int mid=l+r>>1; pushdown(p); if (y<=mid)update1(x,y,l,mid,p<<1,t); else if (x>mid)update1(x,y,mid+1,r,p<<1^1,t); else update1(x,mid,l,mid,p<<1,t),update1(mid+1,y,mid+1,r,p<<1^1,t); pushup(p); } void update2(int x,int y,int l,int r,int p,int t) { if (x==l&&y==r){ mx1[p]=min(mx1[p],t); mx2[p]=min(mx2[p],t); return; } int mid=l+r>>1; pushdown(p); if (y<=mid)update2(x,y,l,mid,p<<1,t); else if (x>mid)update2(x,y,mid+1,r,p<<1^1,t); else update2(x,mid,l,mid,p<<1,t),update2(mid+1,y,mid+1,r,p<<1^1,t); pushup(p); } void build(int l,int r,int p) { if (l==r){ printf("%d ",mx1[p]); return; } int mid=l+r>>1; pushdown(p); build(l,mid,p<<1); build(mid+1,r,p<<1^1); } int main() { n=read(),m=read(); for (i=1;i<=m;i++){ opt=read(); l=read(),r=read(),x=read(); l++;r++; if (opt==1) update1(l,r,1,n,1,x); else update2(l,r,1,n,1,x); } } build(1,n,1); }
又臭又长+1
两个更新可以合在一起的，但是懒得改了