「KTSC 2022 R1」飞扬的小鸟 题解

问题分析

我们需要在二维平面上找到一条最优路径，使得小鸟经过的线段权重和最大。路径由三段组成：

1. 从起点 $(0, y_1)$ 水平飞行到转折点 $(x_t, y_1)$
2. 在 $x_t$ 处垂直上升到 $(x_t, y_2)$ 或下降到 $(x_t, y_2)$
3. 从 $(x_t, y_2)$ 水平飞行到终点 $(W, y_2)$

关键约束：

• 只能进行一次垂直移动（上升或下降）
• 不能飞出边界 $[0, H]$
• 线段与坐标轴平行

核心思路

问题转化

将问题转化为在扫描线+线段树框架下求解：

1. 坐标离散化：将坐标乘以2并加1，避免边界问题
2. 扫描线处理：按x坐标扫描，维护当前列的信息
3. 线段树优化：使用线段树维护不同y坐标的得分

算法框架

代码采用双向扫描策略：

• 第一次扫描处理上升情况
• 第二次扫描处理下降情况（通过坐标翻转）
• 取两次扫描的最大值

代码详解

数据结构定义

struct rect {
    int x1, x2, y1, y2, val;  // 线段的边界和权重
};

struct node {
    ll ans;           // 当前最大得分
    ll val[2];        // val[0]: 上半段得分, val[1]: 下半段得分  
    ll tag[2];        // 懒标记
};

线段树设计

线段树维护三个关键值：

• val[0]：从当前y位置向上飞行的最大得分
• val[1]：从当前y位置向下飞行的最大得分
• ans：整体最大得分 = max(val[0] + val[1])

inline void push_up(const int &x) {
    tr[x].ans = std::max({tr[x<<1].ans, tr[x<<1|1].ans, 
                         tr[x<<1].val[0] + tr[x<<1|1].val[1]}) +
                tr[x].tag[0] + tr[x].tag[1];
    tr[x].val[0] = std::max(tr[x<<1].val[0], tr[x<<1|1].val[0]) + tr[x].tag[0];
    tr[x].val[1] = std::max(tr[x<<1].val[1], tr[x<<1|1].val[1]) + tr[x].tag[1];
}

扫描线算法

ll _solve(const int &w, const int &h, const int &n) {
    SGT::build(h);  // 初始化线段树
    
    // 准备扫描线事件
    for (int i = 1; i <= n; i++) {
        p[i] = {a[i].x1, i};        // 线段开始
        p[n + i] = {a[i].x2 + 1, -i}; // 线段结束
        SGT::modify<1>(a[i].y1, a[i].y2, a[i].val);  // 初始加入下半段
    }
    
    std::sort(p + 1, p + (n << 1) + 1);  // 按x坐标排序
    
    ll tag(0), res(ninf);
    for (int i = 1, j = 1; i <= w; i++) {
        // 处理当前x坐标的所有事件
        while (j <= n << 1 && std::get<0>(p[j]) == i) {
            if (std::get<1>(p[j]) > 0) {
                // 线段开始：从下半段移到上半段
                const int id(std::get<1>(p[j]));
                SGT::modify<1>(a[id].y1, a[id].y2, -a[id].val);
                tag += a[id].val;
                SGT::modify<0>(a[id].y2 + 1, h, -a[id].val);
                SGT::modify<1>(1, a[id].y1 - 1, -a[id].val);
            } else {
                // 线段结束：从上段移回下半段  
                const int id(-std::get<1>(p[j]));
                tag -= a[id].val;
                SGT::modify<0>(a[id].y2 + 1, h, a[id].val);
                SGT::modify<1>(1, a[id].y1 - 1, a[id].val);
                SGT::modify<0>(a[id].y1, a[id].y2, a[id].val);
            }
            ++j;
        }
        
        res = std::max(res, SGT::tr[1].ans + tag);
    }
    return res;
}

双向处理

ll solve(const int &w, const int &h, const int &n) {
    ll tmp(_solve(w, h, n));  // 处理上升情况
    
    // 坐标翻转，处理下降情况
    for (int i = 1; i <= n; i++) {
        a[i].y1 = h + 1 - a[i].y1;
        a[i].y2 = h + 1 - a[i].y2;
        std::swap(a[i].y1, a[i].y2);
    }
    
    tmp = std::max(tmp, _solve(w, h, n));
    return tmp;
}

算法正确性

扫描线逻辑

对于每个x坐标：

• 线段开始：该线段从"下半段飞行"转为"跨越转折点"
• 线段结束：该线段从"跨越转折点"转回"下半段飞行"
• tag变量：记录当前列所有线段的权重和（完整经过的线段）

得分计算

• val[1]：从当前y向下飞行到边界的得分
• val[0]：从当前y向上飞行到边界的得分
• ans：找到最优的转折点y，使得 上半段得分 + 下半段得分 最大

复杂度分析

时间复杂度

• 排序：$O(N \log N)$
• 扫描线：$O(W + N \log H)$
• 线段树操作：每次 $O(\log H)$
• 总复杂度：$O((N + W) \log H)$

空间复杂度

• 线段树：$O(H)$
• 事件数组：$O(N)$
• 总空间：$O(N + H)$

算法优势

$1.$ 统一处理：通过坐标翻转，用同一套逻辑处理上升和下降 $2.$ 高效扫描：扫描线避免重复计算 $3.$ 线段树优化：$O(\log H)$ 时间维护复杂状态 $4.$ 边界处理：坐标变换避免复杂的边界判断

适用场景

该算法适用于：

• 二维平面路径优化问题
• 包含转折点的路径规划
• 需要处理大量平行于坐标轴的障碍物
• 实时性要求较高的场景

总结

本题通过巧妙的扫描线设计和线段树优化，将复杂的路径规划问题转化为高效的数据结构问题。算法在 $O((N+W)\log H)$ 时间内解决了大规模数据的最优路径查找，体现了扫描线和线段树在几何问题中的强大应用。