这题看别人题解的

这题说可以转换成数据备份。

这题可以把一段同号的数并成一个数，那么就变成了一个正负交替的序列，然后把头尾的负数去掉。

然后就是把所有的正值都加起来，并统计正数的段数cnt，如cnt<=m,那么这些整数的和就是答案

如果cnt>m,那我们就要不断地去掉一段，直到cnt=m

先把所有数的绝对值加进优先队列，每次去一个最小的出来然后减掉，最后的即为答案。

为什么是正确的呢？因为如果减去的值在原数列中为正则相当于不要这个数，否则就相当于选了这个负数然后把两边的正值合并起来。

无论减去正数还是负数，都要保证每次操作能够使段数cnt-1，这是我们的目的所在

既如果去掉的是正数，保证了cnt-1，如果去掉了负数，那么要保证它的两边必须要是正数，这样才能使旁边两个正数加上这个负数，使得我们原来取的它的旁边的两段正数加上这个负数后，段数减一，所以处于左右端点的负数都要先去掉

但有一个问题，就是若选了一个数那么其两边的数就必定不能被选，那么就转换成了数据备份了。

 

真的是被这题搞得快自闭了，自己写的一直wa,经过不断修改代码，两个代码来回交，大概交了40次，才发现我哪里错了

错的 l[pos] = l[l[pos]];r[pos] = r[r[pos]];r[l[l[pos]]] = pos;l[r[r[pos]]] = pos;

这个是导致我WA了20次的原因，怎么也没想到是这个地方错了，我还在疯狂修改其他地方。

对的r[l[l[pos]]] = pos;l[r[r[pos]]] = pos;l[pos] = l[l[pos]];r[pos] = r[r[pos]];

原来错的那个我的 l[pos] 已经先更改过了。

#include
      
       using namespace std;typedef unsigned long long ull;const int maxn = 1e5 + 5;int a[maxn], l[maxn], r[maxn],n,m,ans,cnt;bool vis[maxn];struct data{    int val, pos;    data(int val1 = 0, int pos1 = 0) { val = val1; pos = pos1; }    bool operator < (const data &a) const    {        return a.val
       
         que;int main(){    cin >> n >> m;    int tot = 1;    for (int i = 1; i <= n; i++)    {        int tmp;        cin >> tmp;        if (a[tot] * tmp >= 0) a[tot] += tmp;        else a[++tot] = tmp;    }    int left = 1;    if (a[1]<0) left++;    if (a[tot]<0) tot--;    for (int i = left; i <= tot; i++)    {        if (a[i] > 0) cnt++, ans += a[i];        a[i] = abs(a[i]);        que.push(data(a[i],i));        //que.push(data(a[i],i));        l[i] = i - 1;        r[i] = i + 1;    }    l[left]=r[tot] = 0;    if (cnt <= m) cout << ans << endl;    else    {        int num = cnt - m;        for (int i = 1; i <= num;i++)        {            while (vis[que.top().pos] && !que.empty())  que.pop();            int pos = que.top().pos;            que.pop();            ans -= a[pos];            if (!l[pos])             {                vis[pos] = vis[r[pos]] = true;                l[r[r[pos]]] = 0;            }            else if (!r[pos])            {                vis[pos] = vis[l[pos]]=true;                r[l[l[pos]]] = 0;            }            else            {                vis[l[pos]] = vis[r[pos]] = true;                a[pos] = a[l[pos]] + a[r[pos]] - a[pos];                que.push(data(a[pos],pos));                r[l[l[pos]]] = pos;                l[r[r[pos]]] = pos;                l[pos] = l[l[pos]];                r[pos] = r[r[pos]];            }        }        cout << ans << endl;    }    return 0;}