前言
似乎这题有
O
(
n
n
√
)
的做法，但是我并没有想到。。
一个
n
5
/
3
的做法就想死我了，好吧。。
第一次搞用凸包维护这些东西的题。。以前都没有写过
题解
我们发现，如果我们把一个区间，他的数字个数当做x，和当做y，把他看做坐标系上的点
然后对于加上k后的最大值，其实就是你画一条斜率为-k的线，从y轴的无限大掉下来，第一个碰到的点，在y轴上的截距就是最大值
我们可以发现，k明显是递增的，因为加上的数
>
0
我们就可以用一个上凸的凸包来维护这些东西
由于斜率递增，最优点肯定是单调向右移的
就可以搞了
对于修改操作，就采取暴力重构的方法，所以吧块的大小设为
n
1
/
3
就可以了
对于询问操作，就用正常的合并方式就可以了
维护左边右边的最大值维护类似
CODE：（巨长巨慢空间巨大）
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const LL N=50005;
const LL MAX=(1LL<<55);
const LL size=40;
inline LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
LL n,m;
LL a[N];
LL belong[N];
struct P{LL x,y;};
double xielv (P x,P y){return (double)(x.y-y.y)/(double)(x.x-y.x);}
struct tb
{
LL top,o;
P a[size+5];
void Ins (P x)//现在假如了这个点
{
while (top>1&&xielv(x,a[top-1])>=xielv(a[top],a[top-1])) top--;
a[++top]=x;
}
void move (LL x)//斜率直线移动
{
while (o<top&&xielv(a[o],a[o+1])>=x) o++;
}
};
struct qq
{
LL l,r,k;//范围 这个块加了多少
LL num;
tb s[3];
void rebuild ()
{
num=0;
for (LL u=l;u<=r;u++) a[u]+=k,num+=a[u];
LL n=r-l+1;k=0;
s[0].o=s[1].o=s[2].o=1;
s[0].top=s[1].top=s[2].top=0;
for (LL u=1;u<=n;u++)
{
LL lalal=0;
for (LL i=1;i<=u;i++) lalal=lalal+a[l+i-1];
P x=(P){u,lalal};
for (LL i=u+1;i<=n;i++)//右端点在哪里
{
lalal=lalal-a[i-u+l-1];
lalal=lalal+a[i+l-1];
x.y=max(x.y,lalal);
}
//printf("shen:%lld %lld\n",x.x,x.y);
s[0].Ins(x);
}
P x=(P){0,0};
for (LL u=1;u<=n;u++)
{
x.y+=a[l+u-1];x.x=u;
s[1].Ins(x);
}
x=(P){0,0};
for (LL u=n;u>=1;u--)
{
x.y+=a[l+u-1];x.x=n-u+1;
s[2].Ins(x);
}
s[0].move(0);s[1].move(0);s[2].move(0);
//printf("OZY:%lld\n",s[0].top);
}
void add (LL x)//区间加
{
num=num+x*(r-l+1);
k+=x;
s[0].move(-k);s[1].move(-k);s[2].move(-k);
}
LL get (LL x)
{
P o=s[x].a[s[x].o];
return o.y+o.x*k;
}
}g[N];
void print()
{
for (int u=1;u<=n;u++) printf("%lld ",a[u]);
printf("\n");
for (LL u=1;u<=n;u++)
printf("%lld ",belong[u]);
printf("\n");
for (LL u=1;u<=belong[n];u++)
printf("%lld L:%lld R:%lld num:%lld 0:%lld 1:%lld 2:%lld\n",u,g[u].l,g[u].r,g[u].num,g[u].get(0),g[u].get(1),g[u].get(2));
printf("\n");
}
int main()
{
n=read();m=read();
for (LL u=1;u<=n;u++) a[u]=read();
for (LL u=1;u<=n;u++)
{
belong[u]=(u-1)/size+1;
g[belong[u]].r=u;
}
for (LL u=1;u<=belong[n];u++)
{
g[u].l=(u-1)*size+1;
g[u].k=0;
g[u].rebuild();
}
// print();
while (m--)
{
char ss[5];
scanf("%s",ss);
if (ss[0]=='Q')//询问
{
LL l,r;
l=read();r=read();
LL ans=0,lalal=0;
if (belong[l]==belong[r])//在一个块里面
{
for (LL u=l;u<=r;u++)
{
lalal=lalal+a[u]+g[belong[l]].k;
if (lalal<0) lalal=0;
ans=max(ans,lalal);
}
printf("%lld\n",ans);
}
else//不在一个块里面
{
LL ans=0,lalal=0;
for (LL u=l;u<=g[belong[l]].r;u++)
{
lalal=lalal+a[u]+g[belong[l]].k;
if (lalal<0) lalal=0;
ans=max(ans,lalal);
}
for (LL u=belong[l]+1;u<belong[r];u++)
{
ans=max(ans,g[u].get(0));
ans=max(ans,g[u].get(1)+lalal);
lalal=max(lalal+g[u].num,g[u].get(2));
if (lalal<0) lalal=0;
}
for (LL u=g[belong[r]].l;u<=r;u++)
{
lalal=lalal+a[u]+g[belong[r]].k;
if (lalal<0) lalal=0;
ans=max(ans,lalal);
}
printf("%lld\n",ans);
}
}
else
{
LL l,r,x;
l=read();r=read();x=read();
if (belong[l]==belong[r])//在这一个块里面
{
for (LL u=l;u<=r;u++) a[u]+=x;
g[belong[l]].rebuild();
}
else
{
for (LL u=l;u<=g[belong[l]].r;u++) a[u]+=x;
g[belong[l]].rebuild();
for (LL u=belong[l]+1;u<belong[r];u++) g[u].add(x);
for (LL u=g[belong[r]].l;u<=r;u++) a[u]+=x;
g[belong[r]].rebuild();
}
}
//print();
}
return 0;
}