题解：P10137 [USACO24JAN] Walking in Manhattan G

· · 题解

神仙倍增题。

注意到，同一条直线上的两个点在进行“两次转弯”后一定还在同一直线（如果能到达），因此令 f_{i,j} 表示从第 i 条水平路线开始，进行 2^j 次“两次转弯”，会到达哪一条水平线。同理，对于竖直路线定义对应的 g_{i,j} 数组。

显然，两条相邻直线间距的奇偶性决定了 f_{i,0} 与 g_{i,0} 的值，而对于所有 j \geq 1，有转移方程 f_{i,j} = f_{f_{i, j - 1},j - 1}，g 数组同理。

计算完倍增数组后，就可以解决问题了。

首先，对于一个点，我们可以二分出离他最近的十字路口。我们以这个十字路口作为新的起点，注意特判走不到十字路口的情况。

其次，只要还可以进行“两次转弯”，我们就根据倍增数组进行。这样可以在 \mathcal{O}(\log n) 的时间复杂度内跳到不足以进行“两次转弯”。

最后，根据已经走过的路程计算终点即可。

参考代码（时间复杂度 \mathcal{O}(q \log n)，可以获得 100 分）：

#include<bits/stdc++.h>
#include<sys/stat.h>
#include<sys/mman.h>
#include<immintrin.h>
#define int long long

namespace detail {
    // Fast IO by masonxiong (%%%)
    // DON'T copy my code
    // But if you want brown tag......
};

class Scanner {
    // Fast Input
} cin;

class Printer {
    // Fast Output
} cout;

int n, q, f[200005][20], g[200005][20];
std::vector<int> heng, shuu;

signed main(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        char ch; cin >> ch;
        if(ch == 'H'){
            int x; cin >> x;
            heng.push_back(x);
        }else{
            int x; cin >> x;
            shuu.push_back(x);
        }
    }
    heng.push_back(1000000086 << 1), shuu.push_back(1000000086 << 1);
    sort(heng.begin(), heng.end()), sort(shuu.begin(), shuu.end());
    for(int j = 0; j < 20; j++){
        f[heng.size() - 1][j] = heng.size() - 1;
        for(int i = (int)heng.size() - 2; ~i; i--){
            if(j == 0){
                f[i][j] = (heng[i + 1] - heng[i]) & 1 ? i + 1 : f[i + 1][0];
            }else{
                f[i][j] = f[f[i][j - 1]][j - 1];
            }
        }
        g[shuu.size() - 1][j] = shuu.size() - 1;
        for(int i = (int)shuu.size() - 2; ~i; i--){
            if(j == 0){
                g[i][j] = (shuu[i + 1] - shuu[i]) & 1 ? i + 1 : g[i + 1][0];
            }else{
                g[i][j] = g[g[i][j - 1]][j - 1];
            }
        }
    }
    // for(int i = 0; i < (int)heng.size(); i++){
    //     for(int j = 0; j < 20; j++){
    //         cout << f[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    // cout << '\n';
    // for(int i = 0; i < (int)shuu.size(); i++){
    //     for(int j = 0; j < 20; j++){
    //         cout << g[i][j] << ' ';
    //     }
    //     cout << '\n';
    // }
    while(q--){
        int x, y, d; cin >> x >> y >> d;
        int heng0 = std::lower_bound(heng.begin(), heng.end(), y) - heng.begin();
        int shuu0 = std::lower_bound(shuu.begin(), shuu.end(), x) - shuu.begin();
        int dis = 0;
        //Step 1
        // cout << "Step 1 Starting!" << '\n';
        if(y != heng[heng0]){
            int runn = heng[heng0] - y;
            if(runn >= d){
                cout << x << ' ' << y + d << '\n';
                continue;
            }
            d -= runn, dis += runn;
            y = heng[heng0];
        }
        if(x != shuu[shuu0]){
            int runn = shuu[shuu0] - x;
            if(runn >= d){
                cout << x + d << ' ' << y << '\n';
                continue;
            }
            d -= runn, dis += runn;
            x = shuu[shuu0];
        }
        //Step 2
        // cout << "Step 2 Starting!" << '\n';
        for(int i = 19; ~i; i--){
            int x = f[heng0][i], y = g[shuu0][i];
            int runn = (heng[x] - heng[heng0]) + (shuu[y] - shuu[shuu0]);
            if(runn <= d){
                d -= runn, dis += runn;
                heng0 = x, shuu0 = y;
            }
        }
        //Step 3
        // cout << "Step 3 Starting!" << '\n';
        if(dis & 1){
            int runn = shuu[g[shuu0][0]] - shuu[shuu0];
            if(runn >= d){
                cout << shuu[shuu0] + d << ' ' << heng[heng0] << '\n';
            }else{
                cout << shuu[g[shuu0][0]] << ' ' << heng[heng0] + d - runn << '\n';
            }
        }else{
            int runn = heng[f[heng0][0]] - heng[heng0];
            if(runn >= d){
                cout << shuu[shuu0] << ' ' << heng[heng0] + d << '\n';
            }else{
                cout << shuu[shuu0] + d - runn << ' ' << heng[f[heng0][0]] << '\n';
            }
        }
    }
    return 0;
}