「Bzoj 2288」生日礼物 (链表+堆)

BZOJ 2288
题意：给出一个长度为$n$的数列，要求从中取出不超过$m$段连续的数，使其和最大。

首先压缩，将符号相同的压成一个元素，0随意放在任意一块位置，那么序列变为一正一负交错序列。
然后考虑没有限制$m$时，选所有正数即可。
如果有限制，我们就可以抛弃某些正数或者加入某些负数使得两个正数合成一块(注意头尾的负数不能取)
我们发现不管负数正数都只关心他的绝对值
然后对于每次操作的点他左右两边的点都是不能取的，所以转化到了Bzoj 1150

链表堆维护即可。注意记录值只需要绝对值，包括之后的任何操作！

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;

    int abss(int x) {return x > 0 ? x : -x;}

    struct data {
        int u, val;
        bool operator < (const data &rhs) const {return val > rhs.val;}
    };
    priority_queue<data > q;

    int n, m, a[MAXN];
    int nn, b[MAXN];
    int tot, h, t, l[MAXN], r[MAXN], val[MAXN], vis[MAXN];

    void ins(int pos, int v) {
        ++tot, val[tot] = v;
        l[r[pos]] = tot;
        r[tot] = r[pos], l[tot] = pos;
        r[pos] = tot;
    }
    void del(int pos) {
        vis[pos] = 1;
        r[l[pos]] = r[pos], l[r[pos]] = l[pos];
    }

    void clean() {
        ms(vis, 0);
        tot = 1, h = 0, t = 1;
        l[t] = h, r[h] = t, val[0] = val[1] = 1000000002;
    }
    int solve() {
        clean();
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        nn = -1;
        int now = 0, tjz = 0, totz = 0;
        for (int i = 1; i <= n; ++i) {
            if (i == 1 || a[i] * now < 0) {
                b[++nn] = now;
                if (now > 0) ++tjz, totz += now;
                now = 0;
            }
            now += a[i];
        }
        if (now > 0) ++tjz, totz += now;
        b[++nn] = now;
        int hh = 1;
        if (b[1] < 0) ++hh;
        if (b[nn] < 0) --nn;
        ins(h, b[hh]), q.push((data){tot, abss(b[hh])});
        for (int i = hh + 1; i <= nn; ++i) ins(tot, b[i]), q.push((data){tot, abss(b[i])});
        int nd = tjz - m;
        if (nd <= 0) return cout << totz << endl, 0;
        while (!q.empty()) {
            data p = q.top(); q.pop();
            if (vis[p.u]) continue ;
            if (val[p.u] < 0 && ((l[p.u] == h) || (r[p.u] == t))) continue ;
            totz -= p.val;
            val[p.u] = abss(val[l[p.u]]) + abss(val[r[p.u]]) - abss(val[p.u]);
            if (l[p.u] != h || l[p.u] != t) del(l[p.u]);
            if (r[p.u] != h || r[p.u] != t) del(r[p.u]);
            q.push((data){p.u, abss(val[p.u])});
            --nd;
            if (!nd) break ;
        }
        return cout << totz << endl, 0;
        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}