T179940 分段校验

一道动态规划线段树优化题解
少有的整个文章由AI生成

题目原文

T179940 分段校验

题目描述

给定一个数组 $a$ 和一个定值 $m$ 。你需要将序列 $a$ 分成若干连续段，对于一段 $a_l,...,a_r$ ，定义其校验值为本段之和与定值 $m$ 之差的绝对值，即 $|(\sum_{i=l}^ra_i) - m|$ 。

请你对序列进行分段，使得所有段的校验值之和最小。

例如 $a = [1,-2,3], m = 4$ ：

若分段为 $[1,-2,3]$ ，答案为 $2$
若分段为 $[1,-2],[3]$ ，答案为 $5+1 = 6$
若分段为 $[1],[-2,3]$ ，答案为 $3+3 = 6$
若分段为 $[1],[-2],[3]$ ，答案为 $3+6+1 = 10$

最优答案为 $2$ 。

输入格式

第一行，包含两个整数 $n, m$ ，表示数组长度和给定定值

第二行，包含 $n$ 个整数 $a_i$ ，表示该数组

输出格式

输出一行，包含一个整数，表示答案

输入输出样例 #1

输入 #1

3 4
1 -2 3

输出 #1

输入输出样例 #2

输入 #2

10 2
3 0 5 -1 -2 5 -1 -7 0 6

输出 #2

输入输出样例 #3

输入 #3

10 1
-2 -1 -4 -1 4 2 5 0 4 -3

输出 #3

说明/提示

数据范围

对于 $20\%$ 的数据， $1 \le n,m \le 10,-10 \le a_i \le 10$

对于 $40\%$ 的数据， $1 \le n,m \le 1000,-1000 \le a_i \le 1000$

对于另 $20\%$ 的数据， $1 \le n,m \le 10^5, 0 \le a_i \le 10^3$

对于 $100\%$ 的数据， $1 \le n,m \le 10^5,-1000 \le a_i \le 1000$

要解决这个问题，我们可以使用动态规划（Dynamic Programming, DP）结合高效的数据结构（如线段树或 Fenwick 树）来优化转移过程。具体步骤如下：

问题分析

我们需要将数组 $a$ 分成若干连续段，使得每段的校验值之和最小。对于一个段 $[l, r]$ ，其校验值为 $|(\sum_{i=l}^r a_i) - m|$ 。设前缀和为 $s[i] = \sum_{k=1}^i a_k$ ，则校验值可以表示为 $|s[r] - s[l-1] - m|$ 。

定义动态规划状态：

$dp[i]$ ：表示前 $i$ 个元素分段后的最小校验值之和。

则状态转移方程为：

dp[i] = \min_{0 \leq j < i} \{ dp[j] + |s[i] - s[j] - m| \}

直接计算会导致时间复杂度为 $O(n^2)$ ，对于 $n \leq 10^5$ 的数据量是不合适的。因此，我们需要优化这一过程，使其达到 $O(n \log n)$ 的时间复杂度。

优化思路

我们需要高效地计算每个 $i$ 对应的 $\min_{j < i} \{ dp[j] + |s[i] - m - s[j]| \}$ 。观察到这是一个对于每个 $i$ ，寻找 $s[j]$ 最接近 $s[i] - m$ 的问题，可以借助数据结构如有序集合（std::set）或者线段树来进行高效查询。

分解绝对值

将绝对值拆分成两种情况：

$s[j] \leq s[i] - m$ ，此时 $|s[i] - m - s[j]| = s[i] - m - s[j]$ ，对应的最小值为 $dp[j] - s[j]$ 加上 $s[i] - m$ 。
$s[j] \geq s[i] - m$ ，此时 $|s[i] - m - s[j]| = s[j] - (s[i] - m)$ ，对应的最小值为 $dp[j] + s[j]$ 减去 $s[i] - m$ 。

因此， $dp[i]$ 可以表示为：

dp[i] = \min \left( \min_{s[j] \leq x} \{ dp[j] - s[j] \} + x, \min_{s[j] \geq x} \{ dp[j] + s[j] \} - x \right)

其中 $x = s[i] - m$ 。

为了高效查询，我们可以使用两个线段树：

一个存储 $dp[j] - s[j]$ ，用于查询 $s[j] \leq x$ 的最小值。
另一个存储 $dp[j] + s[j]$ ，用于查询 $s[j] \geq x$ 的最小值。

离散化前缀和

由于前缀和可能范围较大，我们需要先对所有前缀和进行离散化，给每个唯一的 $s[j]$ 分配一个唯一的索引。

实现步骤

计算前缀和：
计算数组的所有前缀和 $s[0 \ldots n]$ 。
离散化前缀和：
将所有的 $s[j]$ 排序去重，并为每个唯一的 $s[j]$ 分配一个索引。
初始化动态规划和数据结构：
- 设置 $dp[0] = 0$ 。
- 初始化两个线段树，分别用于存储 $dp[j] - s[j]$ 和 $dp[j] + s[j]$ 。
动态规划转移：
对于每个 $i$ 从 $1$ 到 $n$ ：
- 计算 $x = s[i] - m$ 。
- 查找 $s[j] \leq x$ 的最小 $dp[j] - s[j]$ 。
- 查找 $s[j] \geq x$ 的最小 $dp[j] + s[j]$ 。
- 计算 $dp[i]$ 为上述两者的最小值。
- 将 $dp[i] - s[i]$ 和 $dp[i] + s[i]$ 更新到对应的线段树中。
输出结果：
最终答案为 $dp[n]$ 。

代码实现

以下是基于上述思路的 C++ 实现：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 定义一个极大值
const ll INF = 1e18;

// 线段树支持区间最小查询和点更新
struct SegmentTree {
    int n;
    vector<ll> tree;

    SegmentTree(int size) {
        n = 1;
        while(n < size) n <<= 1;
        tree.assign(2*n, INF);
    }

    // 更新位置 pos (0-based) 的值为val
    void update(int pos, ll val) {
        pos += n;
        tree[pos] = min(tree[pos], val);
        while(pos > 1){
            pos >>= 1;
            tree[pos] = min(tree[2*pos], tree[2*pos+1]);
        }
    }

    // 查询区间 [l, r) 的最小值
    ll query(int l, int r) const {
        ll res = INF;
        int left = l + n;
        int right = r + n;
        while(left < right){
            if(left & 1){
                res = min(res, tree[left++]);
            }
            if(right & 1){
                res = min(res, tree[--right]);
            }
            left >>= 1;
            right >>= 1;
        }
        return res;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll m;
    cin >> n >> m;
    vector<ll> a(n);
    for(auto &x:a) cin >> x;
    
    // 计算前缀和
    vector<ll> s(n+1, 0);
    for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i-1];
    
    // 离散化前缀和
    vector<ll> all_s = s;
    // 还需要 x = s[i] - m
    for(int i=0;i<=n;i++) all_s.push_back(s[i] - m);
    sort(all_s.begin(), all_s.end());
    all_s.erase(unique(all_s.begin(), all_s.end()), all_s.end());
    
    // 映射 s[j] 和 x 到离散化后的索引
    auto get_idx = [&](ll val) -> int {
        return lower_bound(all_s.begin(), all_s.end(), val) - all_s.begin();
    };
    
    int size = all_s.size();
    // 初始化两个线段树
    SegmentTree st1(size); // 存 dp[j] - s[j]
    SegmentTree st2(size); // 存 dp[j] + s[j]
    
    // 初始化 dp[0] = 0
    // 插入 j=0 的情况
    st1.update(get_idx(s[0]), 0 - s[0]);
    st2.update(get_idx(s[0]), 0 + s[0]);
    
    // 初始化 dp array
    // 可以不存储全 dp array，因为只需要 dp[j] 继续更新下去
    vector<ll> dp(n+1, INF);
    dp[0] = 0;
    
    for(int i=1;i<=n;i++){
        ll x = s[i] - m;
        // 找到 x 在 all_s 中的离散化索引
        // 对于 st1，查询 s[j] <= x
        // 找最大的 s[j] <= x，即 upper_bound(x) - 1
        int pos1 = upper_bound(all_s.begin(), all_s.end(), x) - all_s.begin() - 1;
        ll res1 = INF;
        if(pos1 >= 0){
            res1 = st1.query(0, pos1+1) + x;
        }
        // 对于 st2，查询 s[j] >= x
        // 找最小的 s[j] >= x，即 lower_bound(x)
        int pos2 = lower_bound(all_s.begin(), all_s.end(), x) - all_s.begin();
        ll res2 = INF;
        if(pos2 < size){
            res2 = st2.query(pos2, size) - x;
        }
        // 取两者最小值作为 dp[i]
        dp[i] = min(res1, res2);
        // 更新线段树
        st1.update(get_idx(s[i]), dp[i] - s[i]);
        st2.update(get_idx(s[i]), dp[i] + s[i]);
    }
    
    cout << dp[n] << "\n";
}

代码说明

前缀和计算：
- 计算数组的前缀和 s[i] = s[i-1] + a[i-1]，其中 s[0] = 0。
离散化前缀和：
- 将所有的 s[j] 和 s[j] - m 收集到 all_s 中并去重排序。
- 使用二分查找（lower_bound）将每个 s[j] 和 x = s[i] - m 映射到离散化后的索引。
线段树结构：
- 自定义的 SegmentTree 类支持区间最小查询和点更新。
- st1 用于存储 dp[j] - s[j]，支持查询 s[j] <= x 的最小值。
- st2 用于存储 dp[j] + s[j]，支持查询 s[j] >= x 的最小值。
动态规划转移：
- 对于每个位置 i，计算 x = s[i] - m。
- 使用 st1 查询所有 s[j] <= x 的最小 dp[j] - s[j]，然后加上 x 得到一个候选值。
- 使用 st2 查询所有 s[j] >= x 的最小 dp[j] + s[j]，然后减去 x 得到另一个候选值。
- 取两者的最小值作为 dp[i]。
- 将新的 dp[i] - s[i] 和 dp[i] + s[i] 更新到对应的线段树中，以便后续的查询。
输出结果：
最终的最优解为 dp[n]。

复杂度分析

时间复杂度： $O(n \log n)$ ，主要来自于前缀和的计算、离散化和线段树的查询与更新。
空间复杂度： $O(n)$ ，用于存储前缀和、离散化后的值以及动态规划数组和线段树。

注意事项

数据范围：
- 前缀和可能会超过 32 位整数范围，因此使用 long long（即 ll）来存储前缀和和动态规划数组。
离散化：
- 确保离散化后的索引正确对应到原始的 s[j] 和 x，避免漏掉边界情况。
初始化：
- dp[0] 初始化为 0，表示没有分段的初始状态。
线段树极大值的设置：
- 线段树初始值设置为一个足够大的数（如 1e18），确保在查询时不会影响最小值的计算。

示例

以用户提供的第一个样例为例：

输入：
3 4
1 -2 3

输出：
2

计算前缀和：s = [0, 1, -1, 2]
离散化前缀和和 x = s[i] - m = [-4, -3, -5, -2]，合并并排序后得到 all_s = [-5, -4, -3, -2, 0, 1, 2]
通过动态规划和线段树的查询与更新，最终计算得到 dp[3] = 2。

结论

通过将动态规划与线段树结合起来，可以有效地将时间复杂度从 $O(n^2)$ 降低到 $O(n \log n)$ ，使得该算法适用于较大的数据量。这种方法特别适用于需要在动态转移中进行区间最小值查询的问题。

T179940 分段校验

题目原文

T179940 分段校验

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

输入输出样例 #2

输入 #2

输出 #2

输入输出样例 #3

输入 #3

输出 #3

说明/提示

数据范围

问题分析

优化思路

分解绝对值

离散化前缀和

实现步骤

代码实现

代码说明

复杂度分析

注意事项

示例

结论

外链分享

集合位运算

Zengtudor