[文章目录]
Description
ftiasch 18岁生日的时候，lqp18_31给她看了一个神奇的序列 A1, A2, ..., AN. 她被允许选择不超过 M 个连续的部分作为自己的生日礼物。
自然地，ftiasch想要知道选择元素之和的最大值。你能帮助她吗？n,m<=10^5
一段连续的正值显然是会一起选的，但是有可能由于段数只有m个的限制而包含一些负值的段，所以所选的连续部分只包含极长的连续的正、负段。
将连续的正值缩到一个位置，连续的负值也缩到一个位置，那么序列就变成了正负相邻的一个序列。
现在假设正的段数不超过m，那么答案就是所有正数的和。
否则，考虑缩段，每次将一段缩到相邻两段上。将负的缩到两边正的上相当于选负的，将正的缩到两边负的上相当于不选正的。
按照数的绝对值排序，从小到大进行缩段即可。这样缩段的代价一定是最小的。缩到m个正段时，正段的权值和即为答案。
注意边界的负段直接舍去，因为不会使正段的个数减少。
复杂度nlogn
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
int n,m,tot,ans,a[N],pre[N],nxt[N];
bool vis[N];
struct node
{
int id,w;
};
bool operator <(node x,node y){return x.w>y.w;}
priority_queue<node>q;
int main()
{
scanf("%d%d",&n,&m);
int i;
for(i=1;i<=n;++i) scanf("%d",a+i);
while(n>=1&&a[n]<=0) --n;
for(i=1;i<=n;++i) if(a[i]!=0)
{
if(a[i]>0) (tot&1) ? a[tot]+=a[i] : a[++tot]=a[i];
else (tot&1) ? a[++tot]=-a[i] : a[tot]+=-a[i];
}
for(i=1;i<=tot;i+=2) ans+=a[i];
m=(tot>>1)+(tot&1)-m;
for(i=1;i<=tot;++i) pre[i]=i-1,nxt[i]=i+1;
pre[0]=0; nxt[0]=1; pre[tot+1]=tot; nxt[tot+1]=tot+1;
for(i=1;i<=tot;++i) q.push((node){i,a[i]});
int x;
while(m>0)
{
--m;
while(vis[q.top().id]) q.pop();
x=q.top().id; q.pop();
ans-=a[x];
vis[pre[x]]=vis[nxt[x]]=1;
if(pre[x]!=0&&nxt[x]!=tot+1)
{
q.push((node){x,a[x]=a[pre[x]]+a[nxt[x]]-a[x]});
pre[x]=pre[pre[x]]; nxt[pre[x]]=x;
nxt[x]=nxt[nxt[x]]; pre[nxt[x]]=x;
}
else
{
nxt[pre[pre[x]]]=nxt[x];
pre[nxt[nxt[x]]]=pre[x];
}
}
printf("%d\n",ans);
return 0;
}