https://www.luogu.org/problemnew/show/P1121
不会做啊。。。
看题解讲的：
答案的两段可能有两种情况：一是同时包含第1和第n个，2是不同时包含第1和第n个
对于第二种可以先求出f[i],g[i]分别表示1..i和i..n的最大子段和，然后枚举断点解决
对于第一种可以转化成找到“序列上最小两段字段和“去掉，这可以用第二种的方法解决；不过注意这个”序列上最小两段字段和“长度必须<=n-2（因为要剩下至少2个元素），需要一些特判
另外，话说此题居然还能用线段树维护...
（然而数据弱，仍然不知道以下代码是不是对的）
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
#define int ll
struct pii
{
int fi,se;
pii():fi(),se(){}
pii(int a,int b):fi(a),se(b){}
};
pii max1(const pii &a,const pii &b)
{
return (a.fi<b.fi||(a.fi==b.fi&&a.se>b.se))?b:a;
}
pii min1(const pii &a,const pii &b)
{
return (a.fi<b.fi||(a.fi==b.fi&&a.se<b.se))?a:b;
}
int a[];
pii f1[],g1[],f2[],g2[];
int n,a1,a2,sum;
int calc(int p)
{
if(p==)
{
return g2[].se==n- ? g2[].fi-max(a[],a[n]) : g2[].fi;
}
else if(p==n)
{
return f2[n-].se==n- ? f2[n-].fi-max(a[],a[n-])
: f2[n-].fi;
}
else
{
return f2[p-].se+g2[p+].se==n-
? f2[p-].fi+g2[p+].fi - max(max(a[],a[p-]),
max(a[p+],a[n]))
: f2[p-].fi+g2[p+].fi;
}
}
signed main()
{
int i;pii t;
scanf("%lld",&n);
if(n<=) exit(-);
for(i=;i<=n;++i)
{
scanf("%lld",&a[i]);
sum+=a[i];
}
f1[]=pii(a[],);
t=pii(a[],);
if(t.fi<=) t=pii(,);
for(i=;i<=n;++i)
{
t.fi+=a[i];++t.se;
f1[i]=max1(f1[i-],t);
if(t.fi<=) t=pii(,);
}
g1[n]=pii(a[n],);
t=pii(a[n],);
if(t.fi<=) t=pii(,);
for(i=n-;i>=;--i)
{
t.fi+=a[i];++t.se;
g1[i]=max1(g1[i+],t);
if(t.fi<=) t=pii(,);
}
f2[]=pii(a[],);
t=pii(a[],);
if(t.fi>=) t=pii(,);
for(i=;i<=n;++i)
{
t.fi+=a[i];++t.se;
f2[i]=min1(f2[i-],t);
if(t.fi>=) t=pii(,);
}
g2[n]=pii(a[n],);
t=pii(a[n],);
if(t.fi>=) t=pii(,);
for(i=n-;i>=;--i)
{
t.fi+=a[i];++t.se;
g2[i]=min1(g2[i+],t);
if(t.fi>=) t=pii(,);
}
a1=f1[].fi+g1[].fi;
for(i=;i<=n-;++i)
a1=max(a1,f1[i].fi+g1[i+].fi);
a2=calc();
for(i=;i<=n;++i)
a2=min(a2,calc(i));
printf("%lld",max(a1,sum-a2));
return ;
}