魔法应用后地图高度差最大值分析

题目分析

题目要求计算在应用任意子集的魔法后，地图中最高列和最低列的高度差的最大值。每个魔法应用于一个区间，使区间内每列高度减少一个正权重，每个魔法最多使用一次。

关键观察

• 最终高度差定义为 ，其中 ， 是覆盖列 的所有被选魔法的权重之和
• 高度差可以表示为
• 对于任意列对 ，通过选择合适的魔法子集， 可以达到下界
• 因此，最大高度差为

优化计算

直接枚举所有列对 的复杂度为 ，不可接受。需要优化：

• 重新整理表达式：
  
  其中：
  • 是同时覆盖 和 的魔法权重之和
  • 是覆盖列 的所有魔法权重之和
  • 
• 对于固定 ， 可以通过维护一个支持区间加和全局最大值查询的数据结构（如线段树）高效计算
• 当 从 1 到 递增时，覆盖 的魔法集合 变化：在 处添加左端点为 的魔法，删除右端点为 的魔法。使用滑动窗口维护

算法步骤

1. 初始化：

   • 读入 和
   • 读入高度数组
   • 初始化线段树，叶节点 存储 ，支持区间加（统一加减值）和全局最大值查询
   • 创建两个列表（数组或向量）add 和 remove，大小 ，初始为空。用于存储每个位置添加和删除的魔法信息
   • 初始化全局和 （维护 ），最大高度差

2. 预处理魔法：

   • 对于每个魔法 （参数 ）：
     • 将 加入 add[L_i]
     • 如果 ，将 加入 remove[R_i + 1]（因为魔法在 时不再覆盖当前列）

3. 主循环（ 从 1 到 ）：

   • 添加魔法：对于 add[k] 中的每个魔法 ：
     • 线段树在区间 上执行区间加 （因为应用魔法会减少高度）
     • 更新
   • 删除魔法：对于 remove[k] 中的每个魔法 ：
     • 线段树在区间 上执行区间加 （撤销魔法影响）
     • 更新
   • 计算当前值：
     • 
     • 线段树的全局最大值（即 ）
     • 
     • 更新

4. 输出结果： 即为最大高度差

复杂度分析

• 预处理：读入和初始化
• 线段树操作：每个魔法添加和删除各一次，每次区间加操作 ，总复杂度
• 主循环： 次迭代，每次查询全局最大值
• 总复杂度：，满足

代码实现（C++）

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

const long long INF = 1e18; // 定义无穷大常量，用于初始化答案

// 线段树结构体，支持区间加和全局最大值查询
struct SegmentTree {
    int n; // 线段树管理的区间长度
    vector<long long> tree; // 线段树节点数组
    vector<long long> lazy; // 懒标记数组，用于延迟更新
    
    // 构造函数：初始化线段树
    SegmentTree(int size, const vector<long long>& arr) {
        n = size;
        tree.resize(4 * n); // 分配4倍空间
        lazy.resize(4 * n, 0); // 初始化懒标记为0
        build(1, 1, n, arr); // 从根节点开始建树
    }

    // 递归构建线段树
    void build(int node, int l, int r, const vector<long long>& arr) {
        // 到达叶子节点
        if (l == r) {
            tree[node] = arr[l]; // 存储原始数组值
            return;
        }
        int mid = (l + r) / 2; // 计算中点
        build(node * 2, l, mid, arr); // 递归构建左子树
        build(node * 2 + 1, mid + 1, r, arr); // 递归构建右子树
        // 更新当前节点：存储左右子树的最大值
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    // 下推懒标记到子节点
    void push(int node, int l, int r) {
        // 如果当前节点有懒标记
        if (lazy[node] != 0) {
            tree[node] += lazy[node]; // 更新当前节点值
            
            // 如果不是叶子节点，将懒标记传递给子节点
            if (l != r) {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }
            lazy[node] = 0; // 清除当前节点的懒标记
        }
    }

    // 区间更新操作：[ql, qr]区间内的值增加val
    void update(int node, int l, int r, int ql, int qr, long long val) {
        push(node, l, r); // 处理当前节点的懒标记
        
        // 当前区间与查询区间无交集
        if (qr < l || r < ql) return;
        
        // 当前区间完全包含在查询区间内
        if (ql <= l && r <= qr) {
            lazy[node] += val; // 更新懒标记
            push(node, l, r); // 下推更新
            return;
        }
        
        // 部分重叠，递归更新左右子树
        int mid = (l + r) / 2;
        update(node * 2, l, mid, ql, qr, val); // 更新左子树
        update(node * 2 + 1, mid + 1, r, ql, qr, val); // 更新右子树
        
        // 更新当前节点：取左右子树的最大值
        tree[node] = max(tree[node * 2], tree[node * 2 + 1]);
    }

    // 查询全局最大值（直接返回根节点值）
    long long query() {
        return tree[1]; // 根节点存储全局最大值
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, m; // n: 列数, m: 魔法数量
    cin >> n >> m;
    vector<long long> H(n + 1); // 存储每列的初始高度
    
    // 读取高度数据
    for (int i = 1; i <= n; i++) {
        cin >> H[i];
    }

    // 初始化线段树，叶节点存储初始高度
    vector<long long> arr(n + 1);
    for (int i = 1; i <= n; i++) {
        arr[i] = H[i];
    }
    SegmentTree segTree(n, arr); // 创建线段树实例

    // 定义添加和删除魔法的容器
    // add[i]: 在位置i开始生效的魔法
    // remove[i]: 在位置i结束生效的魔法
    vector<vector<tuple<int, int, long long>>> add(n + 2);
    vector<vector<tuple<int, int, long long>>> remove(n + 2);

    // 读取所有魔法信息
    for (int i = 0; i < m; i++) {
        int L, R; // 魔法的左右边界
        long long W; // 魔法的权重
        cin >> L >> R >> W;
        
        // 记录在L位置添加该魔法
        add[L].emplace_back(L, R, W);
        
        // 记录在R+1位置移除该魔法（如果R+1不超过n）
        if (R + 1 <= n) {
            remove[R + 1].emplace_back(L, R, W);
        }
    }

    long long sum = 0; // 当前列k被覆盖的魔法权重总和
    long long ans = -INF; // 存储最终答案（最大高度差）

    // 主循环：从左到右处理每一列k
    for (int k = 1; k <= n; k++) {
        // 处理在k位置开始的魔法
        for (auto& spell : add[k]) {
            // 解包魔法参数
            int L = get<0>(spell), R = get<1>(spell);
            long long W = get<2>(spell);
            
            // 在线段树的[L,R]区间减去权重W（应用魔法）
            segTree.update(1, 1, n, L, R, -W);
            
            // 更新当前覆盖的魔法权重总和
            sum += W;
        }

        // 处理在k位置结束的魔法（即从k-1位置结束）
        for (auto& spell : remove[k]) {
            // 解包魔法参数
            int L = get<0>(spell), R = get<1>(spell);
            long long W = get<2>(spell);
            
            // 在线段树的[L,R]区间加回权重W（撤销魔法）
            segTree.update(1, 1, n, L, R, W);
            
            // 更新当前覆盖的魔法权重总和
            sum -= W;
        }

        // 计算当前列k的B_k值
        long long B_k = H[k] - sum;
        
        // 查询当前全局最大值M_k = max_j(H_j - I_jk)
        long long M_k = segTree.query();
        
        // 计算当前高度差候选值C_k = M_k - B_k
        long long C_k = M_k - B_k;
        
        // 更新全局最大高度差
        ans = max(ans, C_k);
    }

    // 输出最终答案
    cout << ans << endl;

    return 0;
}

代码说明

1. 线段树：支持区间加和全局最大值查询。update 方法使用懒标记优化区间加操作，query 方法直接返回根节点值（全局最大值）
2. 魔法处理：add 和 remove 列表存储每个位置需要添加或删除的魔法（元组 ）
3. 主循环：
   • 添加魔法：在 处添加左端点为 的魔法，更新线段树和
   • 删除魔法：在 处删除右端点为 的魔法，更新线段树和
   • 计算 ：查询线段树全局最大值 ，计算 ，更新答案
4. 输出：最终 即为最大高度差

此算法高效地利用了线段树和滑动窗口技术，确保在 时间内解决问题