题解：P13077 [NOISG 2019] Feast

· · 题解

题解很多线段树维护最大子段和是何意味，来一发单调队列的反悔贪心。\\ 显然能将同符号的子段合并，将每一个子段的和记为 val_i，现将所有正的子段记录答案，假设取出来 x 个子段。当 x\le k 时显然就是答案，考虑大于时怎么处理，减少选出的区间个数有两种方法，一种是将两个正子段中间的负子段也选上，合并成一个大的区间，还有一种就是直接不选某个正子段。\\

  1. 将两个正子段和中间的负子段合并 设中间负子段的下标为 i。\ 如果当前的负子段为边界，那么显然直接扔掉即可。\ 此次合并的代价为 -val_i，然后 val_i 变为 val_{l_i}+val_{r_i}+val_i，即考虑再把这个负子段和左右两个正子段都不选的价值，再把左右两个正子段删去。
  2. 直接不选某个正子段 设中间正子段的下标为 i。\ 此次合并的代价为 val_i，然后 val_i 变为 val_{l_i}+val_{r_i}+val_i，即考虑再把这个正子段和左右两个负子段都选的价值，再把左右两个负子段删去。

发现每次的代价就是 val_i 的绝对值，直接去最小的未删去的子段即可。\ 直接用单调队列维护 val_i 的绝对值的最小值，链表维护删除左右两边的子段即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll read() {
    ll x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=x*10+ch-48;
        ch=getchar();
    }
    return x*f;
}
const ll N=1e6+10;
ll n,k;
ll a[N],tot,sum,ans;
struct Item{
    ll val,l,r;
    bool det;
}t[N];
priority_queue<pair<ll,ll> > q;
void del(ll x){
    t[x].det=1;
    t[t[x].l].r=t[x].r;
    t[t[x].r].l=t[x].l;
    t[x].det=1;
}
signed main(){
    n=read();
    k=read();
    for (int i=1;i<=n;i++){
        a[i]=read();
        if(a[i]==0) continue;
        if((a[i]<0&&t[tot].val>=0)||(a[i]>0&&t[tot].val<=0)) t[++tot].val=a[i];
        else t[tot].val+=a[i];
    }
    for (int i=1;i<=tot;i++){
        t[i].l=i-1;
        t[i].r=i+1;
        if(t[i].val>0) ans+=t[i].val,sum++;
        q.push(make_pair(-abs(t[i].val),i));
    }
    while(sum>k){
        while(t[q.top().second].det) q.pop();
        ll pos=q.top().second;
        q.pop();
        if((t[pos].l==0||t[pos].r==tot+1)&&t[pos].val<=0) continue;//两边直接删去
        sum--;
        ans-=abs(t[pos].val);
        t[pos].val=t[t[pos].l].val+t[t[pos].r].val+t[pos].val;
        if(t[pos].l>=1) del(t[pos].l);
        if(t[pos].r<=tot) del(t[pos].r);
        q.push(make_pair(-abs(t[pos].val),pos));
    }
    printf("%lld\n",ans);
}