CF280D k-Maximum Subsequence Sum 题解

题意：

给定长度为 \(n\) 的数列和 \(m\) 个询问，要求支持：

修改某个位置的值。

询问区间 \([l,r]\) 里选出至多 \(k\) 个不相交的子段和的最大值。

数据范围：

\(1 \le n,m \le 10^5,~|a_i| \le 500,~0\le k \le 20\) 。

初学模拟费用流，好像没想象中那么难懂。

考虑以下费用流模型：

\(S\) 向每个 \(i\) 连边，容量为 \(1\) ，费用为 \(0\) ，其中 \(1 \le i \le n\) 。
每个 \(i\) 向 \(i + 1\) 连边，容量为 \(1\) ，费用为 \(a_i\) ，其中 \(1 \le i < n\) 。
每个 \(i\) 向 \(T'\) 连边，容量为 \(1\) ，费用为 \(0\) ，其中 \(1 \le i \le n\) 。
\(T'\) 向 \(T\) 连边，容量为 \(c\) ，费用为 \(0\) ，其中 \(0 \le c \le k\) 。

那么问题就变成了对于每个 \(c\) ，\(S\) 到 \(T\) 的最大费用最大流。

不过这个费用流模型直接跑显然是复杂度爆炸的，这就引出模拟费用流了

模拟费用流的基本思想是用数据结构等工具，去模拟费用流的增广操作

可以发现，每次增广只会增加 \(1\) 的流量，即选择一个 \(i\) 出发。

由于我们不会选择同起点/终点的区间，所以每次增广只会增加一个区间。

而退流的操作，相当于把他们交集部分取反，再求正常的答案。

比如第一次选择了区间 \([1,4]\) ，我们把它取反

这样第二次如果选择了区间 \([3,6]\) ，得到的答案就是区间 \([1,2]\) 和 \([5,6]\) 。

由于 \(k\) 很小，所以重复 \(k\) 次，就可以得到答案了。如果增广的贡献为 \(0\) 可以直接退出循环。

现在我们需要快速维护区间最大子段和、区间取反操作。

后者可以通过打 tag 和维护区间最小子段和来实现

另外由于我们取反了一些区间，所以我们还得记录取反了哪些区间，询问完再翻回来。

时间复杂度 \(\mathcal{O}(qk\log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n, a[N];
struct rec { int l, r, s; };
rec operator+(const rec& x, const rec& y) { return {x.l, y.r, x.s + y.s}; }
bool operator<(const rec &x, const rec& y) { return x.s < y.s; }
void rev(rec& x) { x.s = -x.s; }
struct node { rec max, min, lmax, rmax, lmin, rmin, sum; bool tag; } tr[N * 4];
void init(int x, int k, int at)
{
    tr[at].max = {x, x, k}; tr[at].lmax = {x, x, k}; tr[at].rmax = {x, x, k};
    tr[at].min = {x, x, k}; tr[at].lmin = {x, x, k}; tr[at].rmin = {x, x, k};
    tr[at].sum = {x, x, k}; tr[at].tag = 0;
}
node merge(const node &x, const node &y)
{
    node res;
    res.max = max({x.max, y.max, x.rmax + y.lmax});
    res.min = min({x.min, y.min, x.rmin + y.lmin});
    res.lmax = max(x.lmax, x.sum + y.lmax);
    res.rmax = max(y.rmax, x.rmax + y.sum);
    res.lmin = min(x.lmin, x.sum + y.lmin);
    res.rmin = min(y.rmin, x.rmin + y.sum);
    res.sum = x.sum + y.sum; res.tag = 0; return res;
}
void push_up(int at) { tr[at] = merge(tr[ls(at)], tr[rs(at)]); }
void proc(int at)
{
    swap(tr[at].max, tr[at].min);
    swap(tr[at].lmax, tr[at].lmin); swap(tr[at].rmax, tr[at].rmin);
    rev(tr[at].max); rev(tr[at].min);
    rev(tr[at].lmax); rev(tr[at].rmax);
    rev(tr[at].lmin); rev(tr[at].rmin);
    rev(tr[at].sum); tr[at].tag ^= 1;
}
void push_down(int at)
{
    if(tr[at].tag)
    {
        proc(ls(at)); proc(rs(at));
        tr[at].tag = 0;
    }
}
void modify(int x, int k, int l = 1, int r = n, int at = 1)
{
    if(l == r) return init(l, k, at);
    push_down(at); int mid = (l + r) >> 1;
    if(x <= mid) modify(x, k, l, mid, ls(at));
    else modify(x, k, mid + 1, r, rs(at));
    push_up(at);
}
void update(int nl, int nr, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr) return proc(at);
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(nl, nr, l, mid, ls(at));
    if(nr > mid) update(nl, nr, mid + 1, r, rs(at));
    push_up(at);
}
node query(int nl, int nr, int l = 1, int r = n, int at = 1)
{
    if(nl <= l && r <= nr) return tr[at];
    push_down(at); int mid = (l + r) >> 1;
    if(nl > mid) return query(nl, nr, mid + 1, r, rs(at));
    if(nr <= mid) return query(nl, nr, l, mid, ls(at));
    return merge(query(nl, nr, l, mid, ls(at)), query(nl, nr, mid + 1, r, rs(at)));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; rep(i, 1, n) { int x; cin >> x; modify(i, x); }
    int qwq, op, x, y, k; cin >> qwq;
    while(qwq--)
    {
        cin >> op;
        if(op == 0) { cin >> x >> k; modify(x, k); }
        else
        {
            cin >> x >> y >> k;
            int res = 0; static queue<node> q; q = {};
            while(k--)
            {
                auto t = query(x, y); if(t.max.s < 0) break;
                res += t.max.s; update(t.max.l, t.max.r); q.push(t);
            }
            cout << res << '\n';
            while(!q.empty())
            {
                auto t = q.front(); q.pop();
                update(t.max.l, t.max.r);
            }
        }
    }
    return 0;
}