-->http://www.lydsy.com/JudgeOnline/problem.php?id=3064
线段树裸题,维护六个标记,当前最大值,当前加标记,当前覆盖标记,历史最大值,历史最大加标记,历史最大覆盖标记。
#include<cstring> #include<cstdio> #include<algorithm> using namespace std; #define oo -0x7f7f7f7f #define nc() getchar() inline int read(){ int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc()); if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f; }inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());} #define N 100010 int i,j,k,m,n,x,y,a[N],L,R,V,q;bool F; struct tree{int mx,cover,ad,pmx,pcover,pad;}T[N<<2]; #define lson k<<1,l,m #define rson k<<1|1,m+1,r #define max(a,b) ((a)>(b)?(a):(b)) inline void Mx(int&a,int b){if(b>a)a=b;} #define up(k) (T[k].mx=max(T[k<<1].mx,T[k<<1|1].mx),Mx(T[k].pmx,max(T[k<<1].pmx,T[k<<1|1].pmx))) void build(int k,int l,int r){ T[k].cover=T[k].pcover=oo; if(l==r){T[k].mx=T[k].pmx=a[l];return;} int m=l+r>>1;build(lson),build(rson),T[k].pmx=oo,up(k); } #define Pcover(k,v) (Mx(T[k].pmx,v),Mx(T[k].pcover,v)) #define Pad(k,v) (Mx(T[k].pmx,T[k].mx+v),T[k].cover>oo?Mx(T[k].pcover,T[k].cover+v):Mx(T[k].pad,T[k].ad+v)) #define Cover(k,v) (Mx(T[k].pmx,T[k].mx=v),Mx(T[k].pcover,T[k].cover=v),T[k].ad=0) #define Ad(k,v) (Mx(T[k].pmx,T[k].mx+=v),T[k].cover>oo?Mx(T[k].pcover,T[k].cover+=v):Mx(T[k].pad,T[k].ad+=v)) inline void down(int k){ if(T[k].pad)Pad(k<<1,T[k].pad),Pad(k<<1|1,T[k].pad),T[k].pad=0; if(T[k].pcover>oo)Pcover(k<<1,T[k].pcover),Pcover(k<<1|1,T[k].pcover),T[k].pcover=oo; if(T[k].ad)Ad(k<<1,T[k].ad),Ad(k<<1|1,T[k].ad),T[k].ad=0; if(T[k].cover>oo)Cover(k<<1,T[k].cover),Cover(k<<1|1,T[k].cover),T[k].cover=oo; } int ask(int k,int l,int r){ if(L<=l&&R>=r)return F?T[k].pmx:T[k].mx;down(k); int m=l+r>>1,ans=oo; if(L<=m)Mx(ans,ask(lson)); if(R>m)Mx(ans,ask(rson));return up(k),ans; } void change(int k,int l,int r){ if(L<=l&&R>=r){if(F)Cover(k,V);else Ad(k,V);return;}down(k); int m=l+r>>1;if(L<=m)change(lson);if(R>m)change(rson);up(k); } int main(){ for(n=read(),i=1;i<=n;++i)a[i]=read(); for(build(1,1,n),q=read();q--;){ char f;read(f),L=read(),R=read(); if(f=='Q')F=0,printf("%d\n",ask(1,1,n)); else if(f=='A')F=1,printf("%d\n",ask(1,1,n)); else if(f=='P')F=0,V=read(),change(1,1,n); else F=1,V=read(),change(1,1,n); } }
loading...