解题报告
这道极其简（e）单（xin），真的是一道裸（zhi）的（zhang）线段树。
首先，我们需要维护各种奇奇怪怪的域，当前和，当前最大值，历史和，历史最大值，而历史值又不包括当前值，这就导致了lazy操作的pushdown极其好（nan）写。
没有什么好多说的，直接看这个极其漂（chou）亮（lou）的代码= =
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=<<;
inline int read(){
int sum(),f();
char ch(getchar());
while(ch<''||ch>''){
if(ch=='-')
f=-;
ch=getchar();
}
while(ch>=''&&ch<=''){
sum=sum*+ch-'';
ch=getchar();
}
return sum*f;
}
int n,m;
int v[];
int padd[],pset[],pmx[];
int nadd[],nset[],nmx[];
inline int my_max(int a,int b){
return a>b?a:b;
}
inline void pushup(int i){
int l(i<<),r(l|);
pmx[i]=my_max(pmx[l],pmx[r]);
nmx[i]=my_max(nmx[l],nmx[r]);
}
inline void pushdown(int rt){
int ch(rt<<);
for(int i=;i<=;i++){
int nowch(ch+i);
pmx[nowch]=my_max(pmx[nowch],my_max(padd[rt]+nmx[nowch],pset[rt]));
if(nset[rt]==inf){
nmx[nowch]+=nadd[rt];
if(nset[nowch]==inf){
padd[nowch]=my_max(padd[nowch],nadd[nowch]+padd[rt]);
nadd[nowch]+=nadd[rt];
}
else{
pset[nowch]=my_max(pset[nowch],nset[nowch]+padd[rt]);
nset[nowch]=nmx[nowch];
}
}
else{
if(nset[nowch]==inf){
padd[nowch]=my_max(padd[nowch],nadd[nowch]+padd[rt]);
nadd[nowch]+=padd[rt];
}
else
pset[nowch]=my_max(pset[nowch],nmx[nowch]+padd[rt]);
nmx[nowch]=nset[rt];
nset[nowch]=nset[rt];
pset[nowch]=my_max(pset[rt],pset[nowch]);
}
}
nadd[rt]=;
padd[rt]=;
nset[rt]=inf;
pset[rt]=inf;
}
inline void build(int l,int r,int i){
padd[i]=;
pset[i]=inf;
nadd[i]=;
nset[i]=inf;
if(l==r){
pmx[i]=v[l];
nmx[i]=v[l];
return;
}
int lc(i<<),rc(lc|),mid((l+r)>>);
build(l,mid,lc);
build(mid+,r,rc);
pushup(i);
}
inline void update_set(int ll,int rr,int c,int l,int r,int i){
if(ll<=l&&r<=rr){
nset[i]=c;
nmx[i]=c;
pset[i]=my_max(pset[i],nset[i]);
pmx[i]=my_max(pmx[i],nmx[i]);
return;
}
pushdown(i);
int lc(i<<),rc(lc|),mid((l+r)>>);
if(ll<=mid)
update_set(ll,rr,c,l,mid,lc);
if(rr>mid)
update_set(ll,rr,c,mid+,r,rc);
pushup(i);
}
inline void update_add(int ll,int rr,int c,int l,int r,int i){
if(ll<=l&&r<=rr){
nmx[i]+=c;
pmx[i]=my_max(pmx[i],nmx[i]);
if(nset[i]==inf){
nadd[i]+=c;
padd[i]=my_max(padd[i],nadd[i]);
}
else{
nset[i]=nmx[i];
pset[i]=my_max(pset[i],nset[i]);
}
return;
}
pushdown(i);
int lc(i<<),rc(lc|),mid((l+r)>>);
if(ll<=mid)
update_add(ll,rr,c,l,mid,lc);
if(rr>mid)
update_add(ll,rr,c,mid+,r,rc);
pushup(i);
}
inline int query_p(int ll,int rr,int l,int r,int i){
if(ll<=l&&r<=rr)
return pmx[i];
pushdown(i);
int lc(i<<),rc(lc|),mid((l+r)>>);
int ret(inf);
if(ll<=mid)
ret=my_max(ret,query_p(ll,rr,l,mid,lc));
if(rr>mid)
ret=my_max(ret,query_p(ll,rr,mid+,r,rc));
return ret;
}
inline int query_n(int ll,int rr,int l,int r,int i){
if(ll<=l&&r<=rr)
return nmx[i];
pushdown(i);
int lc(i<<),rc(lc|),mid((l+r)>>);
int ret(inf);
if(ll<=mid)
ret=my_max(ret,query_n(ll,rr,l,mid,lc));
if(rr>mid)
ret=my_max(ret,query_n(ll,rr,mid+,r,rc));
return ret;
}
int main(){
n=read();
for(int i=;i<=n;i++)
v[i]=read();
/*for(int i=1;i<=n;i++)
cout<<v[i]<<' ';*/
build(,n,);
m=read();
char op[];
while(m--){
scanf("%s",op);
if(op[]=='Q'){
int x(read()),y(read());
printf("%d\n",query_n(x,y,,n,));
continue;
}
if(op[]=='A'){
int x(read()),y(read());
printf("%d\n",query_p(x,y,,n,));
continue;
}
if(op[]=='P'){
int x(read()),y(read()),z(read());
update_add(x,y,z,,n,);
continue;
}
if(op[]=='C'){
int x(read()),y(read()),z(read());
update_set(x,y,z,,n,);
continue;
}
}//while(1);
}
ps:本以为可以写到200行，后来pushdown强行压了一半，然后各种压行，形成了如此漂（chou）亮（lou）的代码风格= =