最大M子段和 V2

51nod1053

这题还是我们熟悉的M子段和，只不过N,M<=50000。

这题似乎是一个堆+链表的题目啊

开始考虑把所有正数负数锁在一起。

比如： 1 2 3 -1 –2 -3 666 缩成 6 -6 666这样。

然后用一个堆来维护，就是说把所有的负数和正数都扔进堆里，先选所有正数，然后每一次把堆中绝对值最小的数（如果是负数且没有左或右就跳过）和两边合并，链表维护一下。

当然实际实现用的是set…

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <algorithm>

#include <string.h>

#include <vector>

#include <limits>

#include <set>

#include <map>

using namespace std;

int n,m,l[233333],r[233333];

long long a[233333];

typedef pair<long long,int> pii;

set<pii> ps;

void del(int a)

{

    int L=l[a],R=r[a];

    if(L) r[L]=R;

    if(R) l[R]=L;

}

int main()

{

    int N;

    scanf("%d%d",&N,&m);

    long long ans=0,sum=0,ds=0;

    for(int i=1;i<=N;i++)

    {

        int x;

        scanf("%d",&x);

        if((sum>0&&x<0)||(sum<0&&x>0))

        {

            a[++n]=sum;

            ds+=sum>0;

            ps.insert(pii(abs(sum),n));

            sum=0;

        }

        sum+=x;

        if(x>=0) ans+=x;

    }

    a[++n]=sum;

    ds+=sum>0;

    ps.insert(make_pair(abs(sum),n));

    for(int i=1;i<=n;i++) l[i]=i-1, r[i]=(i<n)?i+1:0;

    while(ds>m)

    {

        int cur=ps.begin()->second;

        ps.erase(ps.begin());

        if((a[cur]<0&&(!l[cur]||!r[cur]))||!a[cur]) continue;

        ps.erase(pii(abs(a[l[cur]]),l[cur]));

        ps.erase(pii(abs(a[r[cur]]),r[cur]));

        ans-=abs(a[cur]);

        a[cur]+=a[l[cur]]+a[r[cur]];

        del(l[cur]); del(r[cur]);

        ps.insert(pii(abs(a[cur]),cur));

        --ds;

    }

    printf("%lld\n",ans);

}