官方题解｜机器人

二分
首先，机器人仅能沿横坐标与纵坐标方向移动。基于这一特性，我们可以分别按横坐标和纵坐标，对柱子的信息进行存储。考虑到坐标数值可能较大，使用map进行存储较为合适。

对于横、纵坐标上每个可能出现的点，我们将其存入对应的数组。完成数据存储后，每次机器人移动时，通过二分查找的方法，就能判断机器人当前位置与目标位置之间是否存在柱子。
时间复杂度 (O($(n + q )\log(n)$)

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;

    cin >> n >> m;
    map<i64, vector<i64> > mpx;
    map<i64, vector<i64> > mpy;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        mpx[x].emplace_back(y);
        mpy[y].emplace_back(x);
    }
    for (auto &i: mpx) {
        auto &[_,v] = i;
        sort(v.begin(), v.end());
    }
    for (auto &i: mpy) {
        auto &[_,v] = i;
        sort(v.begin(), v.end());
    }
    i64 nowx = 0, nowy = 0;

    auto sub = [&](vector<i64> &v, i64 x, i64 to) {
        if (v.empty() || v.back() < x - to || v.front() > x) return x - to;
        int l = 0, r = v.size() - 1;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (v[mid] <= x) l = mid;
            else r = mid - 1;
        }
        if (v[l] >= x - to ) return v[l] + 1;
        return x - to;
    };

    auto add = [&](vector<i64> &v, i64 x, i64 to) {
        if (v.empty() || v.front() > x + to || v.back() < x) return x + to;
        int l = 0, r = v.size() - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (v[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if (v[l] <= x + to) return v[l] - 1;
        return x + to;
    };
    for (int i = 1; i <= m; i++) {
        char c;
        i64 z;
        cin >> c >> z;
        if (c == 'r') {
            nowx = add(mpy[nowy], nowx, z);
        } else if (c == 'l') {
            nowx = sub(mpy[nowy], nowx, z);
        } else if (c == 'w') {
            nowy = add(mpx[nowx], nowy, z);
        } else {
            nowy = sub(mpx[nowx], nowy, z);
        }
    }
    cout << nowx << " " << nowy << endl;
}