花环(garland)

首先注意到一个性质: 如果有连续一段魅力值都为正的花，那么如果选择了其中一朵，肯定也就会选完这一整段(但有可能将该段分成若于个区间)，其实对魅力值为负的花也是同理的，因为会选择为
负的只可能是想将两边为正的花拼起来形成一个大区间，那么对原始的花环，我们可以将所有相邻的正魅力值花缩成一朵，相邻的负魅力值花也缩成一朵，得到一个正负相间的新花环.
新花环上如果为正的花不超过\(m\)朵，根据题意我们就可以选走原先所有魅力值为正的花，且显然这样是最优答案，否则的话我们可以假设先将魅力值为正的花全部选走，再考虑做出一部分牺牲，也即放弃一些魅力值为正的花，或是选择一些魅力值为负的话来连接两段魅力值为正的花
容易看出这个牺牲可以按照花的魅力值绝对值从小到大贪心，但是直接贪心是有问题的，例如对于两段负魅力值的花中问来着的一段正魅力值的花，是有可能同时选择这两段负魅力值的花来连接三段花的，但是如果贪心选择了最中间的正魅力值花放弃就会失去这种选择那么我们可以在选择到某一段花时，将它左右两段花同时删除，再在原位置插入一段新的话，其值等于三段花的值之和，如果再次贪心选择到新插入的花，就表示刚才的贪心需要反悔，实则是选择两段为负的花来连接三段为正的花才是最优的.
贪心可以用一个堆来维护，而这个插入的过程可以用双向链表来维护，总复杂度为\(0(nlogn)\)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<algorithm>
#include<queue>
#define MAXN 300005
using namespace std;
inline int read()
{
    int num=0,sgn=1;
    char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if (ch=='-')sgn=-1,ch=getchar();
    while (ch>='0'&&ch<='9')num*=10,num+=ch-'0',ch=getchar();
    return num*sgn;
}
int n,m,f[MAXN],top,st[MAXN];
int ans,tot;
int val[MAXN],pre[MAXN],nxt[MAXN];
bool del[MAXN];
priority_queue<pair<int,int> >h;
int main()
{
    n=read();m=read();
    for (int i=1;i<=n;i++)
        f[i]=read();
    st[top=1]=f[1];
    for (int i=2;i<=n;i++)
        if (f[i]*f[i-1]>=0)st[top]+=f[i];
        else st[++top]=f[i];
    while (st[top]*st[1]>=0)
        st[1]+=st[top--];
    for (int i=1;i<=top;i++)
        if (st[i]>0)ans+=st[i],tot++;
    if (tot>m)
    {
        for (int i=1;i<=top;i++)
        {
            val[i]=(st[i]>0)?st[i]:(-st[i]);
            pre[i]=i-1;
            nxt[i]=i+1;
            h.push(make_pair(-val[i],i));
        }
        pre[1]=top;nxt[top]=1;
        while (tot>m)
        {
            tot--;
            pair<int,int>p=h.top();h.pop();
            while (del[p.second])p=h.top(),h.pop();
            ans+=p.first;
            val[p.second]=val[pre[p.second]]+val[nxt[p.second]]-val[p.second];
            del[pre[p.second]]=del[nxt[p.second]]=1;
            pre[p.second]=pre[pre[p.second]];nxt[pre[p.second]]=p.second;
            nxt[p.second]=nxt[nxt[p.second]];pre[nxt[p.second]]=p.second;
            h.push(make_pair(-val[p.second],p.second));
        }
    }
    printf("%d\n",ans);
    return 0;
}