P10137

Xycxxx · 2026-05-13 16:13:47 · 题解

来个神 Eterna 的不用倍增的做法。但是和倍增做法本质相同。

考虑会改变方向的情况，就是当前点到交叉路口的长度是奇数。

将所有长度为偶数的边删去，新建一个图，则答案形如：

• 从 (x,y) 开始，走到第一个交叉路口 (x',y')。
• 从 (x',y') 开始，走到第一个在新建的图上也是交叉路口的位置 (x'',y'')。
• 此时在新建的图上每经过一个交叉路口都会改变方向，二分经过了多少个交叉路口，满足走的路程 \le d。
• 剩下的部分因为不会再改变方向，直接暴力做一下，\mathcal{O}(1)。

代码实现细节还是有点多，不过 Eterna 认为非常的好写。

时间复杂度 \mathcal{O}((n+q)\log n)，空间复杂度 \mathcal{O}(n)。 ::::success[code]

#include <bits/stdc++.h>
#define int long long
#define rd read()
using namespace std;
inline int read() {
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    return x;
}
const int N = 2e5 + 5, inf = 1e18;
int n, q;
vector<int> px, Px, py, Py;
map<int, int> vx, vy;
signed main() {
    n = rd, q = rd;
    for (int i = 1; i <= n; ++i) {
        char c; cin >> c; int v = rd;
        if (c == 'H') py.push_back(v), vy[v] = 1;
        else px.push_back(v), vx[v] = 1;
    }
    sort(px.begin(), px.end()); sort(py.begin(), py.end());
    if (px.size()) {
        Px.push_back(px[0]);
        for (int i = 1; i < px.size(); ++i) 
            if ((px[i] - px[i - 1]) & 1) Px.push_back(px[i]);
    }
    if (py.size()) {
        Py.push_back(py[0]);
        for (int i = 1; i < py.size(); ++i) 
            if ((py[i] - py[i - 1]) & 1) Py.push_back(py[i]);
    }
    px.push_back(inf), py.push_back(inf), Px.push_back(inf), Py.push_back(inf);
    for (int i = 1, d, x, y; i <= q; ++i) {
        x = rd, y = rd, d = rd;
        int t = 0, f = 0,
        X = upper_bound(px.begin(), px.end(), x) - px.begin(),
        Y = upper_bound(py.begin(), py.end(), y) - py.begin();
        if (vx[x]) {
            if (py[Y] - y >= d) {cout << x << ' ' << y + d << '\n'; f = 1;}
            else d -= py[Y] - y, t += py[Y] - y, y = py[Y];
        } else {
            if (px[X] - x >= d) {cout << x + d << ' ' << y << '\n'; f = 1;}
            else d -= px[X] - x, t += px[X] - x, x = px[X];
        }
        if (!f) {
            X = upper_bound(Px.begin(), Px.end(), x) - Px.begin();
            Y = upper_bound(Py.begin(), Py.end(), y) - Py.begin();
            if (t & 1) {
                if (Px[X] - x >= d) {cout << x + d << ' ' << y << '\n'; f = 1;}
                else {
                    d -= Px[X] - x, t += Px[X] - x, x = Px[X];
                    if (Py[Y] - y >= d) {cout << x << ' ' << y + d << '\n'; f = 1;}
                    else d -= Py[Y] - y, t += Py[Y] - y, y = Py[Y];
                }
            } else {
                if (Py[Y] - y >= d) {cout << x << ' ' << y + d << '\n'; f = 1;}
                else {
                    d -= Py[Y] - y, t += Py[Y] - y, y = Py[Y];
                    if (Px[X] - x >= d) {cout << x + d << ' ' << y << '\n'; f = 1;}
                    else d -= Px[X] - x, t += Px[X] - x, x = Px[X];
                }
            }
            int l = 1, r = min(Px.size() - X, Py.size() - Y) - 1, res = 0;
            while (l <= r) {
                int mid = l + r >> 1;
                if (Px[X + mid] - Px[X] + Py[Y + mid] - Py[Y] <= d) l = mid + 1, res = mid;
                else r = mid - 1;
            }
            d -= Px[X + res] - Px[X] + Py[Y + res] - Py[Y];
            t += Px[X + res] - Px[X] + Py[Y + res] - Py[Y];
            X += res, Y += res;
            while (!f) {
                if (t & 1) {
                    if (Px[X + 1] - Px[X] >= d) {cout << Px[X] + d << ' ' << Py[Y] << '\n'; f = 1;}
                    else d -= Px[X + 1] - Px[X], t += Px[X + 1] - Px[X], ++X;
                } else {
                    if (Py[Y + 1] - Py[Y] >= d) {cout << Px[X] << ' ' << Py[Y] + d << '\n'; f = 1;}
                    else d -= Py[Y + 1] - Py[Y], t += Py[Y + 1] - Py[Y], ++Y;
                }
            }
        }
    }
    return 0;
}