题解：AT_abc480_g [ABC480G] Zonal Score Minimization

jy_ua · 2026-10-21 18:33:25 · 题解

一道比较经典且浅显的 G 题，拿来练练数据结构优化 DP 还是蛮好的。

题目大意

给你一个长度为 N 的序列，划分成若干个长度 \ge 2 的连续段，使得各段的 \max - \min 之和最小。

思路

这个题面已经把该说的说完了，显然这是一个分段 DP，令 f_i 表示考虑到前 i 个数的划分的最小代价，我们按照题意转移：

这样做是 O(N^2)，挺劣的，所以我们有一个浅显的想法是：用线段树维护括号内一坨。

我们看看具体怎么维护。首先括号内这个式子的主干是 f_j，于是不妨以每个 j 为树的叶子节点。但这样还有一个变量 i，于是我们必须考虑在 i 不断右移的情况下，每个节点值会发生什么变化。

先研究最大值，发现每次从 i 转移到 i+1 时，对于那些区间最大值 \le a_{i+1} 的区间最大值会变为 a_{i+1}。我们继续发现 \max 显然具有单调性，因为所有维护的 \max 本质是一个后缀最大值。那么此时，我们会从 i-1 开始不断往左边更新直到最大值 > a_{i+1}。既然要找到左边第一个大于 a_{i+1} 的位置，单调栈就派上用场了。最小值同理。

此时，只要做到单调栈内维护最大或最小值相同的区间，然后每个 a_i 至多产生一个新区间且至多被合并一次，再加上线段树，整体就能做到 O(NlogN)。

实现

具体地，建一棵线段树维护对于每个 0\le j \le i - 2 的 j 对应的

每次从 i 转移到 i+1 的时候，用两个单调栈存储一些最大或最小值相同的区间，然后考虑 a_{i+1} 的贡献，不断弹掉旧区间，合并成新的区间，对于那些被合并的区间算出它们的变化值，最后用线段树区间更新即可！

特别地，由于线段树维护的是那些 0\le j \le i -2 的 j，所以我们实际上叶子节点对应的 l, r 理应是从 0 开始编号的。

具体细节可看代码及注释。

代码

:::success[AC 代码]

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>
#define LCUR cur << 1
#define RCUR cur << 1 | 1
#define LSON l, mid, LCUR
#define RSON mid + 1, r, RCUR
#define QL ql, qr, LSON
#define QR ql, qr, RSON
#define MID ((l + r) >> 1)

using LL = long long;
const LL INF = 1e18;

enum Option
{
    ADD,
    SET
};

template <typename T>
struct SegmentTree
{
    int size;
    std::vector<T> t, tag;

    SegmentTree(int n) : size(n), t((n << 2) + 5, INF), tag((n << 2) + 5, T()) {}
    void PushUp(int cur) { t[cur] = std::min(t[LCUR], t[RCUR]); }
    void ApplyTag(int cur, const T& fa)
    {
        t[cur] += fa;
        tag[cur] += fa;
    }
    void PushDown(int cur)
    {
        ApplyTag(LCUR, tag[cur]);
        ApplyTag(RCUR, tag[cur]);
        tag[cur] = 0;
    }
    void Update(Option op, T val, int ql, int qr, int l, int r, int cur)
    {
        if (ql <= l && r <= qr)
        {
            if (op == ADD) ApplyTag(cur, val);
            if (op == SET && l == r) t[cur] = val, tag[cur] = 0;
            return;
        }
        int mid = MID;
        PushDown(cur);
        if (ql <= mid) Update(op, val, QL);
        if (qr > mid) Update(op, val, QR);
        PushUp(cur);
    }
    T Query(int ql, int qr, int l, int r, int cur)
    {
        if (ql <= l && r <= qr) return t[cur];
        int mid = MID;
        PushDown(cur);
        T res = INF;
        if (ql <= mid) res = std::min(res, Query(QL));
        if (qr > mid) res = std::min(res, Query(QR));
        return res;
    }
    void Add(int l, int r, T val) { Update(ADD, val, l, r, 0, size - 1, 1); }
    void Set(int pos, T val) { Update(SET, val, pos, pos, 0, size - 1, 1); }
    T Query(int l, int r) { return Query(l, r, 0, size - 1, 1); }
};

int main()
{
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    std::vector<int> a(n + 1, 0);
    for (int i = 1; i <= n; i++) std::cin >> a[i];

    struct Interval // 存储一些最大值或最小值相同的区间
    {
        LL val;
        int l, r;
    };
    SegmentTree<LL> seg(n); // 线段树部分不多介绍
    std::vector<LL> dp(n + 1, INF); 
    std::stack<Interval> max, min; // 两个单调栈
    dp[0] = 0;  // 初始化别忘了
    for (int i = 1; i <= n; i++)
    {
        seg.Set(i - 1, dp[i - 1]); // 首先记录一下上一个的 dp 值
        int l = i - 1; // 然后往前合并区间
        while (!min.empty() && min.top().val >= a[i]) // 如果能够更新最小值
        {
            Interval cur = min.top(); // 弹出旧的区间
            min.pop();
            seg.Add(cur.l, cur.r, cur.val - a[i]); // 区间变化了，线段树中的区间也要受到对应变化量的变化
            l = cur.l; // 记录新区间的左端点
        }
        min.push({a[i], l, i - 1}); // 放入新的区间
        l = i - 1; // 再对最大值做一次
        while (!max.empty() && max.top().val <= a[i])
        {
            Interval cur = max.top();
            max.pop();
            seg.Add(cur.l, cur.r, a[i] - cur.val);
            l = cur.l;
        }
        max.push({a[i], l, i - 1});
        if (i >= 2) dp[i] = seg.Query(0, i - 2); // 查询答案
    }
    std::cout << dp[n];
    return 0;
}

:::