#1076904 (C++17) No.3116 More and more teleporter

• 問題: No.3116 More and more teleporter
• ユーザー: aaaaaaaaaaa
• 提出日時: 2025-04-19 13:35:01
• 言語: C++17 (gcc 13.3.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 146 ms / 2,000 ms
• コード長: 6,131 bytes
• コンパイル時間: 1,183 ms
• コンパイル使用メモリ: 80,256 KB
• 実行使用メモリ: 14,208 KB
• 最終ジャッジ日時: 2025-04-19 13:35:05
• 合計ジャッジ時間: 3,729 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
other	AC * 22

ソースコード

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

// 使用 long long 类型以避免整数溢出
using ll = long long;

// 定义一个非常大的值来表示无穷大
const ll INF = 3e18; 

// 线段树结构体
struct SegmentTree {
    int n; // 原始数组的大小
    std::vector<ll> tree; // 存储线段树节点值的向量

    // 构造函数，初始化线段树
    SegmentTree(int size) {
        n = size;
        // 线段树数组的大小通常需要4倍原始数组大小，+1是为了更安全
        tree.assign(4 * n + 1, INF); 
    }

    // 内部更新函数：递归地更新线段树
    // node: 当前节点索引
    // start, end: 当前节点代表的区间 [start, end]
    // idx: 要更新的原始数组元素的索引
    // val: 新的可能值（用于取最小值）
    void update_internal(int node, int start, int end, int idx, ll val) {
        // 如果到达叶子节点（代表单个元素）
        if (start == end) {
            // 更新叶子节点的值为当前值和新值中的较小者
            tree[node] = std::min(tree[node], val);
            return;
        }
        // 计算中间点，并将区间分为两半
        int mid = start + (end - start) / 2;
        // 如果目标索引在左子区间，则递归更新左子树
        if (idx <= mid) {
            update_internal(2 * node, start, mid, idx, val);
        } 
        // 否则，递归更新右子树
        else {
            update_internal(2 * node + 1, mid + 1, end, idx, val);
        }
        // 更新当前节点的值为左右子节点的最小值
        tree[node] = std::min(tree[2 * node], tree[2 * node + 1]);
    }

    // 内部查询函数：递归地查询区间最小值
    // node: 当前节点索引
    // start, end: 当前节点代表的区间 [start, end]
    // l, r: 查询的目标区间 [l, r]
    ll query_standard(int node, int start, int end, int l, int r) {
        // 如果当前节点代表的区间与查询区间完全没有交集
        if (r < start || end < l) { 
            return INF; // 返回无穷大，表示此区间无贡献
        }
        // 如果当前节点代表的区间完全包含在查询区间内
        if (l <= start && end <= r) { 
             return tree[node]; // 直接返回当前节点存储的最小值
        }
        // 如果当前节点代表的区间与查询区间部分重叠
        int mid = start + (end - start) / 2;
        // 递归查询左子树和右子树
        ll res_left = query_standard(2 * node, start, mid, l, r);
        ll res_right = query_standard(2 * node + 1, mid + 1, end, l, r);
        // 返回左右子树查询结果的最小值
        return std::min(res_left, res_right);
    }

    // 公开的更新接口，使用 1-based 索引
    void update(int idx, ll val) {
         // 检查索引是否在有效范围内 [1, n]
         if (idx < 1 || idx > n) return; 
        // 从根节点（索引1）开始调用内部更新函数
        update_internal(1, 1, n, idx, val);
    }

    // 公开的查询接口，使用 1-based 索引
    ll query(int l, int r) {
        // 如果查询区间的左边界大于右边界，表示空区间
        if (l > r) {
            return INF; // 返回无穷大
        }
        // 确保查询范围在 [1, n] 内
        l = std::max(1, l);
        r = std::min(n, r);
         // 如果调整后的范围无效（例如 l > r）
         if (l > r) return INF;
        // 从根节点（索引1）开始调用内部查询函数
        return query_standard(1, 1, n, l, r);
    }
};

int main() {
    // 禁用 C++ 标准库的同步IO，并解除 cin 和 cout 的绑定，以加速输入输出
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N, Q; // N: 单元格数量, Q: 查询数量
    std::cin >> N >> Q;

    // 创建两个线段树实例
    SegmentTree segA(N); // 用于存储 min(c_t - t)
    SegmentTree segB(N); // 用于存储 min(c_t + t)

    // 处理 Q 个查询
    for (int q = 0; q < Q; ++q) {
        int type; // 查询类型 (1 或 2)
        std::cin >> type;

        if (type == 1) {
            // 查询类型 1: 查找从单元格 1 到单元格 x 的最小成本
            int x;
            std::cin >> x;
            
            // 查询 segA 获取 t <= x 的传送器的 min(c_t - t)
            ll min_A = segA.query(1, x); 
            // 查询 segB 获取 t > x 的传送器的 min(c_t + t)
            ll min_B = segB.query(x + 1, N); 

            ll cost_teleporter = INF; // 初始化通过传送器的成本为无穷大
            
            // 计算通过 t <= x 的传送器到达 x 的成本: c_t + |x - t| = c_t + x - t = x + (c_t - t)
            // 最小成本是 x + min(c_t - t) = x + min_A
            if (min_A != INF) {
                // 使用 (ll)x 确保类型匹配和避免溢出
                cost_teleporter = std::min(cost_teleporter, (ll)x + min_A);
            }
            // 计算通过 t > x 的传送器到达 x 的成本: c_t + |x - t| = c_t + t - x = -x + (c_t + t)
            // 最小成本是 -x + min(c_t + t) = -x + min_B
            if (min_B != INF) {
                 // 使用 (ll)-x 确保类型匹配和避免溢出
                 cost_teleporter = std::min(cost_teleporter, (ll)-x + min_B);
            }

            // 只通过相邻移动到达 x 的成本
            ll cost_adjacent = (ll)x - 1;
            
            // 最终答案是仅相邻移动成本和使用传送器成本中的较小者
            std::cout << std::min(cost_adjacent, cost_teleporter) << "\n";

        } else { 
            // 查询类型 2: 添加一个新的传送器
            int x; // 传送器位置
            ll c;  // 传送器成本
            std::cin >> x >> c;

            // 计算需要在两个线段树中更新的值
            // 使用 (ll)x 进行类型转换
            ll val_A = c - (ll)x; 
            ll val_B = c + (ll)x;
            // 更新两个线段树
            segA.update(x, val_A);
            segB.update(x, val_B);
        }
    }

    return 0;
}