P4314 CPU监控 题解

#include<iostream>#include<cstdio>using namespace std;typedef long long ll;const int N=1e5+13;const ll INF=0x3f3f3f3f3f3f3f3fll;inline ll max(const ll &a,const ll &b){return a>b?a:b;}int n,a[N],m;struct SegTree{int l,r;ll add,preadd,max,premax,set,preset;bool state;}t[N<<2];#define ls p<<1#define rs p<<1|1#define mid ((t[p].l+t[p].r)>>1)inline void refresh(int p){t[p].max=max(t[ls].max,t[rs].max);t[p].premax=max(t[ls].premax,t[rs].premax);}void build(int p,int l,int r){t[p].l=l,t[p].r=r,t[p].max=t[p].premax=-INF;if(l==r){t[p].max=t[p].premax=a[l];return;}build(ls,l,mid);build(rs,mid+1,r);refresh(p);}inline void pushup_set(int p,ll x,ll px){if(!t[p].state){t[p].state=1;t[p].preset=px;t[p].premax=max(t[p].premax,px);}else{t[p].preset=max(t[p].preset,px);t[p].premax=max(t[p].premax,px);}t[p].set=t[p].max=x;}inline void pushup_add(int p,ll x,ll px){if(t[p].state){t[p].preset=max(t[p].preset,t[p].set+px);t[p].premax=max(t[p].premax,t[p].max+px);t[p].set+=x,t[p].max+=x;}else{t[p].preadd=max(t[p].preadd,t[p].add+px);t[p].premax=max(t[p].premax,t[p].max+px);t[p].add+=x,t[p].max+=x;}}inline void pushdown(int p){pushup_add(ls,t[p].add,t[p].preadd);pushup_add(rs,t[p].add,t[p].preadd);t[p].add=t[p].preadd=0;if(t[p].state){pushup_set(ls,t[p].set,t[p].preset);pushup_set(rs,t[p].set,t[p].preset);t[p].state=0,t[p].set=t[p].preset=0;}}void update(int p,int l,int r,ll x){if(l<=t[p].l&&t[p].r<=r) return pushup_add(p,x,x);pushdown(p);if(l<=mid) update(ls,l,r,x);if(r>mid) update(rs,l,r,x);refresh(p);}void modify(int p,int l,int r,ll x){if(l<=t[p].l&&t[p].r<=r) return pushup_set(p,x,x);pushdown(p);if(l<=mid) modify(ls,l,r,x);if(r>mid) modify(rs,l,r,x);refresh(p);}ll query_max(int p,int l,int r){if(l<=t[p].l&&t[p].r<=r) return t[p].max;pushdown(p);ll res=-INF;if(l<=mid) res=max(res,query_max(ls,l,r));if(r>mid) res=max(res,query_max(rs,l,r));return res;}ll query_pre(int p,int l,int r){if(l<=t[p].l&&t[p].r<=r) return t[p].premax;pushdown(p);ll res=-INF;if(l<=mid) res=max(res,query_pre(ls,l,r));if(r>mid) res=max(res,query_pre(rs,l,r));return res;}int main(){scanf("%d",&n);for(int i=1;i<=n;++i) scanf("%d",&a[i]);build(1,1,n);scanf("%d",&m);while(m--){char op[2];int x,y,z;scanf("%s%d%d",op,&x,&y);switch(op[0]){case 'Q':printf("%lld\n",query_max(1,x,y));break;case 'A':printf("%lld\n",query_pre(1,x,y));break;case 'P':scanf("%d",&z);update(1,x,y,z);break;case 'C':scanf("%d",&z);modify(1,x,y,z);break;}}return 0;}