非常有道理。orz EI。
首先单点修改区间最大子段和是 GSS 的经典问题。我们维护出区间和 \(sm\)、最大前缀和 \(lmx\)、最大后缀和 \(rmx\)、最大子段和 \(mx\)，发现这是一种半群信息，直接线段树维护就可以了。
那么对于区间加正数问题，我们依然考虑线段树。线段树想要 pushdown 标记就得先考虑全局加正数。
发现全局加了一个正数后，无论前后缀和最大子段和都倾向于扩大选中的区间长度，这也就表明了假设我们对一个数列不断的全局 +x，那么 \(mx,lmx,rmx\) 关于 \(x\) 都是一个下凸的分段线性函数。这启发我们直接对每一个区间维护一个一次函数。即，对于每一个区间的 \(lmx,rmx,mx\) 我们记录当前状态下它代表的下凸壳上的点所在的那条直线。
我们同时再维护一个 \(lim\) 表示当前区间 \(+lim\) 后，它子树中会存在一个区间的所在直线发生变化。这个信息是很好维护的，我们只需要注意到所有信息的转移都形如取在常数个一次函数中取截距最大的那条转移。那么我们只需要在不是最大的那些函数中与取到了最大值的函数求个交点，然后取交点横坐标最小值就可以了。因为选取的一次函数发生改变当且仅当一条截距小但是斜率大的线“后来居上”。
维护了这些信息后，当我们遇到一个区间加上一数后 \(>lim\) 的情况就暴力往下递归打标记。查询直接按 GSS 的方式查。
这个算法的复杂度证明其实也没有想象中的那么困难。发现我们保持复杂度。下去打球。
#include <cstdio>
#include <algorithm>
#define lc (p<<1)
#define rc (p<<1|1)
using namespace std;
int read(){
char c=getchar();int x=0;bool f=0;
while(c<48||c>57) f|=(c=='-'),c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
if(f) return -x;
return x;
}
const int N=400003;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,q;
ll a[N];
void chmn(ll &x,ll v){if(x>v) x=v;}
struct Line{
int k;ll b;
Line(int K=0,ll B=0):k(K),b(B){}
friend Line operator+(const Line x,const Line y){return Line(x.k+y.k,x.b+y.b);}
friend Line opt(const Line x,const Line y,ll &cur){
if(x.b==y.b){
if(x.k>y.k) return x;
else return y;
}
if(x.b>y.b){
if(x.k<y.k) chmn(cur,(x.b-y.b)/(y.k-x.k));
return x;
}
else{
if(x.k>y.k) chmn(cur,(y.b-x.b)/(x.k-y.k));
return y;
}
}
};
struct Info{
Line sm,lmx,rmx,mx;ll lim;
Info(Line S=Line(),Line L=Line(),Line R=Line(),Line M=Line(),ll Lim=INF):sm(S),lmx(L),rmx(R),mx(M),lim(Lim){}
friend Info operator+(const Info x,const Info y){
ll clim=INF;
Info res(x.sm+y.sm,opt(x.sm+y.lmx,x.lmx,clim),opt(y.sm+x.rmx,y.rmx,clim),opt(opt(x.mx,y.mx,clim),x.rmx+y.lmx,clim),min(x.lim,y.lim));
chmn(res.lim,clim);
return res;
}
}sg[N<<2];
ll tg[N<<2];
int loc[N<<2];
void init(int p){
int x=loc[p];
Line cur(1,a[x]);
if(a[x]<0) sg[p]=Info(cur,Line(),Line(),Line(),-a[x]);
else sg[p]=Info(cur,cur,cur,cur,INF);
}
void build(int p=1,int l=1,int r=n){
if(l==r){loc[p]=l;return init(p);}
int mid=(l+r)>>1;
build(lc,l,mid);
build(rc,mid+1,r);
sg[p]=sg[lc]+sg[rc];
}
void proc(int p,ll v){
if(loc[p]) a[loc[p]]+=v;
tg[p]+=v;
sg[p].sm.b+=sg[p].sm.k*v;
sg[p].lmx.b+=sg[p].lmx.k*v;
sg[p].rmx.b+=sg[p].rmx.k*v;
sg[p].mx.b+=sg[p].mx.k*v;
sg[p].lim-=v;
}
void pushdown(int p){
if(tg[p]){
proc(lc,tg[p]);
proc(rc,tg[p]);
tg[p]=0;
}
}
void update(int sl,int sr,int v,int p=1,int l=1,int r=n){
if(loc[p]){a[loc[p]]+=v;return init(p);}
pushdown(p);
int mid=(l+r)>>1;
if(sl<=l&&r<=sr){
if(sg[p].lim>=v) return proc(p,v);
update(sl,sr,v,lc,l,mid);
update(sl,sr,v,rc,mid+1,r);
}
else{
if(sl<=mid) update(sl,sr,v,lc,l,mid);
if(sr>mid) update(sl,sr,v,rc,mid+1,r);
}
sg[p]=sg[lc]+sg[rc];
}
Info query(int sl,int sr,int p=1,int l=1,int r=n){
if(sl<=l&&r<=sr) return sg[p];
pushdown(p);
int mid=(l+r)>>1;
if(sr<=mid) return query(sl,sr,lc,l,mid);
if(sl>mid) return query(sl,sr,rc,mid+1,r);
return query(sl,sr,lc,l,mid)+query(sl,sr,rc,mid+1,r);
}
int main(){
n=read();q=read();
for(int i=1;i<=n;++i) a[i]=read();
build();
while(q--){
char c=getchar();
while(c!='A'&&c!='Q') c=getchar();
int l=read(),r=read();
if(c=='A') update(l,r,read());
if(c=='Q') printf("%lld\n",query(l,r).mx.b);
}
return 0;
}