【bzoj 5089】最大连续子段和

【bzoj 5089】最大连续子段和

Description

给出一个长度为 n 的序列，要求支持如下两种操作：
A l r x ：将 [l,r] 区间内的所有数加上 x ；
Q l r ： 询问 [l,r] 区间的最大连续子段和。
其中，一个区间的最大连续子段和指的是：该区间所有子区间的区间和中的最大值（本题中子区间包括空区间，区间和为 0 ）。

Input

第一行两个整数 n、m，表示序列的长度以及操作的数目。
之后的 m 行，每行输入一个操作，含义如题目所述。保证操作为 A l r x 或 Q l r 之一。
对于 30% 的数据， n,m≤300 n , m ≤ 300 $n,m≤300$；
对于 60% 的数据， n,m≤1000 n , m ≤ 1000 $n,m≤1000$ ；
对于 100% 的数据， 1≤n,m≤50000,|ai|≤109,1≤x≤40000,1≤l,r≤n 1 ≤ n , m ≤ 50000 , | a i | ≤ 10 9 , 1 ≤ x ≤ 40000 , 1 ≤ l , r ≤ n $1≤n,m≤50000, |a_i |≤10^9, 1≤x≤40000, 1≤l,r≤n$

Output

每个 Q 操作输出一行，表示询问区间的最大连续子段和。

毒瘤题…时限40s…

一眼看上去以为是线段树…但发现不是很可做…

因为带区间加，所以所选择区间的长度可能会增加。

考虑每一个子区间，和随所加的数x的关系式为： sum=(r−l+1)∗x+∑ai s u m = ( r − l + 1 ) ∗ x + ∑ a i $sum=(r-l+1)*x+sum a_i$

其中 ∑ai ∑ a i $sum a_i$ 和 (r−l+1) ( r − l + 1 ) $(r-l+1)$ 是常数，所以我们可以把这个子区间的和看做关于x的一次函数。这样，对于给定的一个x，最大的y就是答案。

显然，我们只要维护下凸壳，就能O(1)计算答案了。

但是一共有 n2 n 2 $n^2$ 个子区间。怎么办呢？

考虑分块。对于每个块维护一个凸壳。修改的时候，因为加的值都是整数，所以x是单调的，用一个指针记录当前块的x值，显然最多跳n次。查询的时候返回x的函数值即可。由于询问需要合并几个块，所以也要维护每个块前缀的凸壳和后缀的凸壳。

对于每一个询问/修改，之间的整块可以直接操作，边上的两个块直接暴力重构。

可以证明，当块的大小为 2∗n13 2 ∗ n 1 3 $2*n^{frac1{3}}$ 时，复杂度最优为 O(n53) O ( n 5 3 ) $Oleft(n^{frac5{3}}right)$。

不过这个题好像有一个根号的做法，可是我不会啊qwq。

#include<cstdio>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
struct point{ll k,b;
};
typedef point P;
int block,pos[100010],a[100010];
int n,m;
bool check(P a,P b,P c)
{double x1=(double)1.0*(b.b-a.b)/(a.k-b.k);double x2=(double)1.0*(c.b-a.b)/(a.k-c.k);if(x1>=x2) return true;return false;
}
double js(P a,P b)
{double x=(double)(b.b-a.b)/(a.k-b.k);return x;
}
struct node2{P a[150];int p,top;void insert(P x){while(top>1&&check(a[top-1],a[top],x)) top--;a[++top]=x;}void move(int x){while(p<top&&js(a[p],a[p+1])<=x) p++;}
}lll;
struct node
{int num,l,r,x;node2 s[3];ll sum;void rebuild(){sum=0;for(int i=l;i<=r;i++) a[i]+=x,sum+=a[i];num=r-l+1,x=0;s[0].top=s[1].top=s[2].top=0;s[0].p=s[1].p=s[2].p=1;for(int len=1;len<=num;len++){ll ksj=0;for(int i=1;i<=len;i++) ksj+=a[i+l-1];P o={len,ksj};for(int i=len+1;i<=num;i++){ksj+=a[i+l-1];ksj-=a[i+l-1-len];o.b=max(o.b,ksj);}s[0].insert(o);}ll ksj=0;for(int i=1;i<=num;i++){ksj+=a[i+l-1];s[1].insert(P{i,ksj});}ksj=0;for(int i=num;i>=1;i--){ksj+=a[i+l-1];s[2].insert(P{num-i+1,ksj});}s[0].p=s[1].p=s[2].p=1;s[0].move(0),s[1].move(0),s[2].move(0);}void update(int k){sum=sum+(r-l+1)*k;x+=k;s[0].move(x),s[1].move(x),s[2].move(x);}ll get(int k){P tmp=s[k].a[s[k].p];return tmp.k*x+tmp.b;}
}g[10010];
inline void init()
{int block=cbrt(n);block*=2;for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1,g[pos[i]].r=i;for(int i=1;i<=pos[n];i++){g[i].l=(i-1)*block+1;g[i].x=0;g[i].rebuild();}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);init();while(m--){int l,r,x;char s[3];scanf("%s",s);if(s[0]=='A'){scanf("%d%d%d",&l,&r,&x);if(pos[l]==pos[r]){for(int i=l;i<=r;i++) a[i]+=x;g[pos[l]].rebuild();}else{int beg=g[pos[l]].l==l?pos[l]:pos[l]+1;int fin=g[pos[r]].r==r?pos[r]:pos[r]-1;for(int i=l;i<g[beg].l;i++) a[i]+=x;if(g[pos[l]].l!=l) g[pos[l]].rebuild();for(int i=beg;i<=fin;i++) g[i].update(x);for(int i=g[fin].r+1;i<=r;i++) a[i]+=x;if(g[pos[r]].r!=r) g[pos[r]].rebuild();}}else{scanf("%d%d",&l,&r);if(pos[l]==pos[r]){ll ksj=0,ans=0;for(int i=l;i<=r;i++){ksj+=a[i]+g[pos[i]].x;if(ksj<0) ksj=0;ans=max(ans,ksj);}printf("%lldn",ans);}else{ll ksj=0,ans=0;int beg=g[pos[l]].l==l?pos[l]:pos[l]+1;int fin=g[pos[r]].r==r?pos[r]:pos[r]-1;for(int i=l;i<g[beg].l;i++){ksj+=a[i]+g[pos[i]].x;if(ksj<0) ksj=0;ans=max(ans,ksj);}for(int i=beg;i<=fin;i++){ans=max(ans,g[i].get(0));ans=max(ans,ksj+g[i].get(1));ksj=max(g[i].get(2),ksj+g[i].sum);if(ksj<0) ksj=0;}for(int i=g[fin].r+1;i<=r;i++){ksj+=a[i]+g[pos[i]].x;if(ksj<0) ksj=0;ans=max(ans,ksj);}printf("%lldn",ans);}}}return 0;
}