题目分析

题目要求选择不超过 (m) 个连续子段，使得子段和最大。核心思路是每次选择当前剩余序列中的最大和连续子段，将其取反（避免重复选择），重复 (m) 次后累加结果。线段树用于高效维护区间最大/最小子段和、前缀/后缀和等信息，支持区间取反操作。

解题思路

1. 线段树维护区间信息：每个节点存储区间和、最大/最小子段和、最大/最小前缀和、最大/最小后缀和。
2. 区间取反操作：通过标记实现区间取反，交换最大/最小相关值并取反。
3. 贪心选择：每次查询当前最大和子段，累加结果后将该子段取反，重复 (m) 次（或直到最大和非正）。

代码实现（带注释）

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int N = 1e6 + 10;

int n, m, a[N];
LL ans;

// 线段树节点结构
struct node {
    LL s;         // 区间和
    LL mx, lx, rx; // 最大子段和、最大前缀和、最大后缀和
    LL mn, ln, rn; // 最小子段和、最小前缀和、最小后缀和
    bool tag;     // 取反标记
} t[N * 4];

// 合并两个节点信息
node operator+(node x, node y) {
    node z;
    z.tag = 0;
    z.s = x.s + y.s;
    // 最大子段和：左区间最大、右区间最大、左后缀+右前缀
    z.mx = max(max(x.mx, y.mx), x.rx + y.lx);
    // 最大前缀和：左前缀或左区间和+右前缀
    z.lx = max(x.lx, x.s + y.lx);
    // 最大后缀和：右后缀或右区间和+左后缀
    z.rx = max(y.rx, y.s + x.rx);
    // 最小子段和：左区间最小、右区间最小、左后缀+右前缀
    z.mn = min(min(x.mn, y.mn), x.rn + y.ln);
    // 最小前缀和：左前缀或左区间和+右前缀
    z.ln = min(x.ln, x.s + y.ln);
    // 最小后缀和：右后缀或右区间和+左后缀
    z.rn = min(y.rn, y.s + x.rn);
    return z;
}

// 构建线段树
void build(int x, int l, int r) {
    if (l == r) {
        // 叶子节点初始化：所有值等于a[l]
        t[x].s = t[x].mn = t[x].mx = t[x].ln = t[x].lx = t[x].rn = t[x].rx = a[l];
        t[x].tag = 0;
        return;
    }
    int mid = (l + r) / 2;
    build(x * 2, l, mid);
    build(x * 2 + 1, mid + 1, r);
    t[x] = t[x * 2] + t[x * 2 + 1]; // 合并左右子节点
}

// 下传取反标记
void downtag(int x, int l, int r) {
    if (t[x].tag == 0) return;
    // 非叶子节点，下传标记到子节点
    if (l != r) {
        t[x * 2].tag ^= 1;
        t[x * 2 + 1].tag ^= 1;
    }
    // 取反操作：交换最大/最小相关值并取反
    t[x].s = -t[x].s;
    swap(t[x].mn, t[x].mx);
    swap(t[x].ln, t[x].lx);
    swap(t[x].rn, t[x].rx);
    t[x].mn = -t[x].mn;
    t[x].mx = -t[x].mx;
    t[x].ln = -t[x].ln;
    t[x].rn = -t[x].rn;
    t[x].lx = -t[x].lx;
    t[x].rx = -t[x].rx;
    t[x].tag = 0; // 清除标记
}

// 区间取反操作
void change(int x, int l, int r, int L, int R) {
    downtag(x, l, r); // 先下传标记
    if (L > r || l > R || L > R) return;
    if (L <= l && r <= R) {
        t[x].tag ^= 1; // 标记取反
        downtag(x, l, r); // 执行取反
        return;
    }
    int mid = (l + r) / 2;
    change(x * 2, l, mid, L, R);
    change(x * 2 + 1, mid + 1, r, L, R);
    t[x] = t[x * 2] + t[x * 2 + 1]; // 合并子节点信息
}

// 查询最大前缀和的右端点
int query1(int x, int l, int r) {
    if (l == r) return l;
    downtag(x, l, r);
    int mid = (l + r) / 2;
    downtag(x * 2, l, mid);
    downtag(x * 2 + 1, mid + 1, r);
    // 最大前缀和来自右子节点的前缀
    if (t[x].lx == t[x * 2].s + t[x * 2 + 1].lx)
        return query1(x * 2 + 1, mid + 1, r);
    return query1(x * 2, l, mid); // 来自左子节点的前缀
}

// 查询最大后缀和的左端点
int query2(int x, int l, int r) {
    if (l == r) return l;
    downtag(x, l, r);
    int mid = (l + r) / 2;
    downtag(x * 2, l, mid);
    downtag(x * 2 + 1, mid + 1, r);
    // 最大后缀和来自左子节点的后缀
    if (t[x].rx == t[x * 2 + 1].s + t[x * 2].rx)
        return query2(x * 2, l, mid);
    return query2(x * 2 + 1, mid + 1, r); // 来自右子节点的后缀
}

// 查询最大子段和的区间
pair<int, int> query(int x, int l, int r) {
    if (t[x].s == t[x].mx) return {l, r}; // 整个区间是最大子段
    downtag(x, l, r);
    int mid = (l + r) / 2;
    downtag(x * 2, l, mid);
    downtag(x * 2 + 1, mid + 1, r);
    if (t[x * 2].mx == t[x].mx)
        return query(x * 2, l, mid); // 最大子段在左区间
    if (t[x * 2 + 1].mx == t[x].mx)
        return query(x * 2 + 1, mid + 1, r); // 最大子段在右区间
    // 最大子段跨左右区间：左区间的最大后缀 + 右区间的最大前缀
    return {query2(x * 2, l, mid), query1(x * 2 + 1, mid + 1, r)};
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n); // 构建线段树
    for (int i = 1; i <= m; i++) {
        if (t[1].mx <= 0) break; // 无正和子段，停止选择
        auto tmp = query(1, 1, n); // 查询当前最大子段
        ans += t[1].mx; // 累加结果
        change(1, 1, n, tmp.first, tmp.second); // 取反该子段
    }
    printf("%lld", ans);
    return 0;
}

代码解释

1. 线段树节点：存储区间和、最大/最小子段和、前缀/后缀和及取反标记。
2. 合并操作：合并左右子节点信息，计算当前节点的最大/最小相关值。
3. 区间取反：通过标记实现高效取反，交换最大/最小相关值并取反。
4. 贪心选择：每次选最大和子段，累加后取反该子段，重复 (m) 次。