19 1

1 6

2 4

2 5

2 7

2 8

3 1

3 3

3 5

3 8

4 1

4 6

4 8

5 2

5 8

6 3

6 4

6 5

6 6

6 7

3 6

可以hack掉这份代码

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

struct DSU {
    std::vector<int> f, mx;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        mx.assign(n, 0);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        mx[x] = max(mx[x], mx[y]);
        f[y] = x;
        return true;
    }

    int size(int x) {
        return mx[find(x)];
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> x(n), y(n), flg(q, 1), a(q), b(q);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }

    for (int i = 0; i < q; i++) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }

    auto work = [&](auto &x, auto &y, auto &a, auto &b) {
        int m = max(ranges::max(y), ranges::max(b)) + 1;
        vector pos(m, vector<int>());
        vector qs(m, vector<pair<int, int>>());
        map<pair<int, int>, int> p;

        for (int i = 0; i < n; i++) {
            p[{x[i], y[i]}] = i;
            pos[y[i]].push_back(i);
        }

        for (int i = 0; i < q; i++) {
            qs[b[i]].emplace_back(a[i], i);
        }

        DSU dsu(n);
        for (int i = 0; i < m; i++) {
            for (auto id : pos[i]) {
                dsu.mx[id] = x[id];
                for (int dx = -1; dx <= 1; dx++) {
                    for (int dy = -1; dy <= 0; dy++) {
                        int nx = x[id] + dx, ny = y[id] + dy;
                        if (p.count({nx, ny})) {
                            dsu.merge(id, p[{nx, ny}]);
                        }
                    }
                }
            }
            vector<pair<int, int>> pre;
            for (auto id : pos[i]) {
                pre.emplace_back(x[id], dsu.size(id));
            }
            for (auto id : pos[i]) {
                dsu.mx[id] = 0;
            }
            sort(all(pre));

            for (int j = 1; j < pre.size(); j++) {
                pre[j].second = max(pre[j].second, pre[j - 1].second);
            }

            for (auto [nx, id] : qs[i]) {
                int l = -1, r = pre.size() - 1;
                while (l < r) {
                    int m = l + r + 1 >> 1;
                    if (pre[m].first < nx) {
                        l = m;
                    } else {
                        r = m - 1;
                    }
                }
                if (l != -1 && pre[l].second > nx) {
                    flg[id] &= 1;
                } else {
                    flg[id] = 0;
                }
            }
        }

        dsu.init(n);
        for (int i = m - 1; i >= 0; i--) {
            for (auto id : pos[i]) {
                dsu.mx[id] = x[id];
                for (int dx = -1; dx <= 1; dx++) {
                    for (int dy = 0; dy <= 1; dy++) {
                        int nx = x[id] + dx, ny = y[id] + dy;
                        if (p.count({nx, ny})) {
                            dsu.merge(id, p[{nx, ny}]);
                        }
                    }
                }
            }
            vector<pair<int, int>> pre;
            for (auto id : pos[i]) {
                pre.emplace_back(x[id], dsu.size(id));
            }
            for (auto id : pos[i]) {
                dsu.mx[id] = 0;
            }
            sort(all(pre));

            for (int j = 1; j < pre.size(); j++) {
                pre[j].second = max(pre[j].second, pre[j - 1].second);
            }

            for (auto [nx, id] : qs[i]) {
                int l = -1, r = pre.size() - 1;
                while (l < r) {
                    int m = l + r + 1 >> 1;
                    if (pre[m].first < nx) {
                        l = m;
                    } else {
                        r = m - 1;
                    }
                }
                if (l != -1 && pre[l].second > nx) {
                    flg[id] &= 1;
                } else {
                    flg[id] = 0;
                }
            }
        }
    };
    work(x, y, a, b);
    work(y, x, b, a);

    for (int i = 0; i < q; i++) {
        if (flg[i]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}