问题描述

题目要求处理一系列航班请求，航班分为南向（从较小编号机场飞往较大编号机场）和北向（从较大编号机场飞往较小编号机场）。每个请求包含起点、终点和最大容量限制。目标是在满足所有请求的前提下，最大化分配的总容量。

输入格式

• K：请求的数量。
• N：机场的数量。
• C：每个机场的最大容量。
• 每个请求包含三个整数 S、E 和 M，分别表示起点、终点和最大容量。

输出格式

输出一个整数，表示在满足所有请求的前提下，可以分配的最大总容量。

算法思路

1. 分类处理：

   • 将南向请求和北向请求分别存储到两个数组中。
   • 南向请求的起点小于终点，北向请求的起点大于终点，北向请求需要转换为起点小于终点的形式。

2. 排序：

   • 按终点对南向请求和北向请求分别进行升序排序。这样可以确保在处理请求时，能够按照终点顺序依次更新线段树。

3. 线段树的应用：

   • 使用线段树来维护每个区间的最大容量。
   • 对于每个请求，查询当前区间的最大容量，计算剩余容量，并尝试分配容量。
   • 如果可以分配容量，则更新线段树，并累加到最终结果中。

4. 独立处理南向和北向请求：

   • 南向和北向请求分别使用独立的线段树，因为它们的区间范围和更新逻辑是独立的。

代码实现

• 使用线段树来高效处理区间更新和查询操作。
• 对南向和北向请求分别排序并处理，确保按照终点顺序更新线段树。
• 在处理每个请求

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 线段树结构，用于高效处理区间更新和查询操作
struct SegmentTree {
private:
    struct Node {
        int max_val;
        int lazy;
        Node() : max_val(0), lazy(0) {}
    };
    vector<Node> tree;   // 线段树的节点数组
    int n;               // 线段树的大小

    // 下推懒惰标记
    void push_down(int node, int l, int r) {
        if (tree[node].lazy != 0) { // 如果当前节点有懒惰标记
            int mid = (l + r) / 2; // 计算中点
            // 将懒惰标记传递给左右子节点
            tree[2 * node].max_val += tree[node].lazy;
            tree[2 * node].lazy += tree[node].lazy;
            tree[2 * node + 1].max_val += tree[node].lazy;
            tree[2 * node + 1].lazy += tree[node].lazy;
            tree[node].lazy = 0; // 清除当前节点的懒惰标记
        }
    }

    // 区间更新操作
    void update(int node, int l, int r, int ul, int ur, int val) {
        if (ul > ur) return; // 如果更新区间无效，直接返回
        if (ul <= l && r <= ur) { // 如果当前节点完全在更新区间内
            tree[node].max_val += val; // 更新当前节点的最大值
            tree[node].lazy += val;    // 设置懒惰标记
            return;
        }
        push_down(node, l, r); // 下推懒惰标记
        int mid = (l + r) / 2; // 计算中点
        // 递归更新左右子节点
        if (ul <= mid) update(2 * node, l, mid, ul, ur, val);
        if (ur > mid) update(2 * node + 1, mid + 1, r, ul, ur, val);
        // 更新当前节点的最大值
        tree[node].max_val = max(tree[2 * node].max_val, tree[2 * node + 1].max_val);
    }

    // 区间查询操作
    int query(int node, int l, int r, int ql, int qr) {
        if (ql > qr) return 0; // 如果查询区间无效，返回0
        if (ql <= l && r <= qr) return tree[node].max_val; // 如果当前节点完全在查询区间内，返回最大值
        push_down(node, l, r); // 下推懒惰标记
        int mid = (l + r) / 2; // 计算中点
        int res = 0; // 初始化结果
        // 递归查询左右子节点
        if (ql <= mid) res = max(res, query(2 * node, l, mid, ql, qr));
        if (qr > mid) res = max(res, query(2 * node + 1, mid + 1, r, ql, qr));
        return res; // 返回查询结果
    }

public:
    // 构造函数，初始化线段树
    SegmentTree(int size) : tree(4 * (size + 2)), n(size) {} // 调整初始化顺序

    // 区间加值操作
    void add(int l, int r, int val) {
        update(1, 1, n, l, r, val); // 调用更新函数
    }

    // 查询区间最大值
    int get_max(int l, int r) {
        return query(1, 1, n, l, r); // 调用查询函数
    }
};

// 请求结构体
struct Request {
    int S, E, M; // 起点、终点、最大值
};

// 比较函数，用于按终点升序排序
struct less_than_Request_E {
    bool operator()(const Request& a, const Request& b) {
        return a.E < b.E;
    }
};

int main() {
    ios_base::sync_with_stdio(false); // 关闭同步
    cin.tie(0);                      // 解绑cin和cout

    int K, N, C; // K: 请求数量，N: 机场数量，C: 每个机场的最大容量
    cin >> K >> N >> C;

    vector<Request> south, north; // 分别存储南向和北向请求
    for (int i = 0; i < K; ++i) {
        int S, E, M; // 输入请求的起点、终点和最大值
        cin >> S >> E >> M;
        if (S < E) {
            south.push_back((Request){S, E, M}); // 南向请求
        } else if (S > E) {
            north.push_back((Request){E, S, M}); // 北向请求，转换为起点小于终点的形式
        }
    }

    int res = 0; // 最终结果

    // 处理南向航班
    sort(south.begin(), south.end(), less_than_Request_E());
    if (N >= 2) {
        SegmentTree st(N - 1); // 初始化线段树，范围为1到N-1
        for (vector<Request>::const_iterator it = south.begin(); it != south.end(); ++it) {
            int l = it->S;
            int r = it->E - 1;
            if (l > r) continue; // 如果区间无效，跳过
            int current_max = st.get_max(l, r); // 查询当前区间的最大值
            int available = C - current_max; // 计算剩余容量
            int add = min(available, it->M); // 计算可以分配的容量
            if (add > 0) {
                res += add; // 更新结果
                st.add(l, r, add); // 更新线段树
            }
        }
    }

    // 处理北向航班
    sort(north.begin(), north.end(), less_than_Request_E());
    if (N >= 2) {
        SegmentTree st(N - 1); // 初始化线段树，范围为1到N-1
        for (vector<Request>::const_iterator it = north.begin(); it != north.end(); ++it) {
            int l = it->S;
            int r = it->E - 1;
            if (l > r) continue; // 如果区间无效，跳过
            int current_max = st.get_max(l, r); // 查询当前区间的最大值
            int available = C - current_max; // 计算剩余容量
            int add = min(available, it->M); // 计算可以分配的容量
            if (add > 0) {
                res += add; // 更新结果
                st.add(l, r, add); // 更新线段树
            }
        }
    }

    cout << res << "\n"; // 输出最终结果

    return 0;
}