「USACO 2023.1 Platinum」Tractor Paths 题解

题目大意

有 $N$ 台拖拉机，第 $i$ 台对应区间 $[l_i, r_i]$，区间端点满足严格单调递增。如果两个拖拉机的区间相交，则它们相邻。需要回答 $Q$ 个查询：

1. 拖拉机 $a$ 到 $b$ 的最短路径长度
2. 至少出现在一条最短路径上的特殊拖拉机数量

解题思路

关键观察

1. 区间图性质：拖拉机形成区间图，最短路径具有特殊结构
2. 跳跃指针：使用倍增法快速计算路径信息
3. 对称性：从左到右和从右到左的路径可以对称处理

算法核心

预处理阶段

1. 解析区间：从LR字符串还原每个拖拉机的左右端点

2. 计算可达范围：

   • pr[i]：从拖拉机 $i$ 向右最远能到达的拖拉机
   • pl[i]：从拖拉机 $i$ 向左最远能到达的拖拉机

3. 倍增数组：

   • R[i][j]：从 $i$ 向右跳 $2^j$ 步到达的位置
   • L[i][j]：从 $i$ 向左跳 $2^j$ 步到达的位置
   • f[i][j]：向右路径上的特殊节点前缀和
   • g[i][j]：向左路径上的特殊节点前缀和

代码解析

#include <bits/stdc++.h>
#define ci const int
#define ll long long
using namespace std;
ci N = 2e5 + 5;

int n, q, l[N], r[N], cl, cr;
int pl[N], pr[N], tp[N], sum[N];
int R[N][18], L[N][18];
ll f[N][18], g[N][18];

int main() {
    scanf("%d%d", &n, &q);
    
    // 解析LR字符串，还原区间端点
    for (int i = 1; i <= n << 1; ++i) {
        char c = getchar();
        while (c != 'L' && c != 'R') c = getchar();
        if (c == 'L') l[++cl] = i;
        else r[++cr] = i;
    }
    
    // 读取特殊节点标记并计算前缀和
    for (int i = 1; i <= n; ++i) {
        char c = getchar();
        while (c != '0' && c != '1') c = getchar();
        tp[i] = c == '1';
        sum[i] = sum[i - 1] + tp[i];
    }
    
    // 计算向右最远可达位置
    for (int i = 1; i <= n; ++i) {
        pr[i] = max(i, pr[i - 1]);
        while (pr[i] < n && l[pr[i] + 1] < r[i]) 
            ++pr[i];
    }
    
    // 计算向左最远可达位置  
    for (int i = n; i; --i) {
        if (i == n) pl[i] = i;
        else pl[i] = min(i, pl[i + 1]);
        while (pl[i] > 1 && r[pl[i] - 1] > l[i])
            --pl[i];
    }
    
    // 初始化倍增数组
    for (int i = 1; i <= n; ++i) {
        R[i][0] = pr[i], L[i][0] = pl[i];
        f[i][0] = sum[pr[i]];      // 向右路径特殊节点和
        g[i][0] = -sum[pl[i] - 1]; // 向左路径特殊节点和
    }
    
    // 构建倍增表
    for (int j = 1; j < 18; ++j) {
        for (int i = 1; i <= n; ++i) {
            R[i][j] = R[R[i][j - 1]][j - 1];
            L[i][j] = L[L[i][j - 1]][j - 1];
            f[i][j] = f[i][j - 1] + f[R[i][j - 1]][j - 1];
            g[i][j] = g[i][j - 1] + g[L[i][j - 1]][j - 1];
        }
    }
    
    // 处理查询
    for (int l, r; q; --q) {
        scanf("%d%d", &l, &r);
        int d = 0;
        
        // 计算最短路径长度（使用倍增）
        for (int i = 17, x = l; ~i; --i) {
            if (R[x][i] < r) {
                x = R[x][i];
                d |= 1 << i;
            }
        }
        printf("%d ", d + 1);  // 路径长度 = 跳数 + 1
        
        // 计算特殊节点数量
        ll ans = 0;
        for (int i = 17, x = l, y = r; ~i; --i) {
            if (d >> i & 1) {
                ans += f[x][i] + g[y][i];
                x = R[x][i];
                y = L[y][i];
            }
        }
        printf("%lld\n", ans + tp[l] + tp[r]);
    }
    
    return 0;
}

算法正确性

最短路径计算

在区间图中，从 $a$ 到 $b$ 的最短路径可以通过贪心策略获得：

• 每次都跳到当前能到达的最远位置
• 使用倍增优化这一过程

特殊节点统计

通过维护前缀和数组：

• f[i][j] 记录从 $i$ 向右跳 $2^j$ 步路径上的特殊节点和
• g[i][j] 记录从 $i$ 向左跳 $2^j$ 步路径上的特殊节点和
• 查询时双向同时跳跃并累加贡献

复杂度分析

• 预处理：$O(n \log n)$
  • 计算可达范围：$O(n)$
  • 构建倍增表：$O(n \log n)$
• 查询：$O(q \log n)$
  • 每个查询 $O(\log n)$

样例验证

对于样例输入：

8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
...

程序正确输出对应的最短路径长度和特殊节点数量，验证了算法的正确性。

总结

本题的解法体现了以下技巧：

1. 区间图建模：利用区间相交关系建立图模型
2. 倍增优化：使用二进制拆分加速路径计算
3. 双向处理：同时从起点和终点出发计算
4. 前缀和技巧：高效统计路径上的特殊节点

这种结合区间图性质和倍增法的思路，对于解决大规模图上的路径查询问题具有很好的参考价值。