线段树(区间覆盖+区间加法)
#include<iostream> #include<cstdio> #include<cctype> #include<cmath> #include<cstring> #include<cstdlib> #include<algorithm> #include<ctime> #define ls (o<<1) #define rs (o<<1|1) using namespace std; const int N =1e6+5; inline int read(){ char x =getchar(); int a =0; while(!isdigit(x)) x =getchar(); while(isdigit(x)) a =a*10+x-48,x =getchar(); return a; } int val[N<<2],add[N<<2],set[N<<2],n; inline void update(int o){ val[o] =max(val[ls],val[rs]); } inline void down(int o){ if(set[o]!=-1){ val[ls] = val[rs] =set[o]; set[ls] = set[rs] =set[o]; add[ls] = add[rs] =0; set[o] =-1; } else if(add[o]){ val[ls] +=add[o]; val[rs] +=add[o]; if(set[ls]==-1){ add[ls] +=add[o]; } else{ set[ls] +=add[o]; } if(set[rs]==-1){ add[rs] +=add[o]; } else{ set[rs] +=add[o]; } add[o] =0; } } inline void modify_set(int o,int l,int r,int ql,int qr,int v){ if(ql<=l&&r<=qr){ val[o] =v; set[o] =v; add[o] =v; return ; } int mid =(l+r) >>1; down(o); if(ql<=mid){ modify_set(ls,l,mid,ql,qr,v); } if(mid+1<=qr){ modify_set(rs,mid+1,r,ql,qr,v); } update(o); } inline void modify_add(int o,int l,int r,int ql,int qr,int v){ if(ql<=l&&r<=qr){ val[o] +=v; if(set[o]==-1){ add[o] +=v; } else{ set[o] +=v; } return ; } int mid =(l+r) >>1; down(o); if(ql<=mid){ modify_add(ls,l,mid,ql,qr,v); } if(mid+1<=qr){ modify_add(rs,mid+1,r,ql,qr,v); } update(o); } inline int query(int o,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr){ return val[o]; } int mid =(l+r) >>1,ans =0; down(o); if(ql<=mid){ ans =max(ans,query(ls,l,mid,ql,qr)); } if(mid+1<=qr){ ans =max(ans,query(rs,mid+1,r,ql,qr)); } return ans; } int main(){ memset(set,-1,sizeof(set)); n =read(); int T =read(); while(T--){ int op =read(),x =read(),y =read(),z; if(op==1){ printf("%d\n",query(1,1,n,x,y)); } else if(op==2){ modify_set(1,1,n,x,y,0); } else{ z =read(),modify_add(1,1,n,x,y,z); } } }
转载于
//www.cnblogs.com/ukcxrtjr/p/11223530.html
Love The Way You Lie
你的名字
港控/mmm°
淩亂°似流年
傷城~
我就是我
不念不忘少年蓝@
还没有评论，来说两句吧...