题解 | #小红的线下查询#

F 小红的线下查询

首先观察到是数点问题，那就想几维数点、扫描线。 观察可得每个点坐标可以转换成 和 两个维度的值，而我们查询的区间是 下部分的 的点有多少，那么我们就可以把 变成一维，用扫描线的思想查询比 小的值加入答案就行了。

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q;
    cin >> n >> q;
    
    vector<array<int, 2>> a(n), b(q);
    vector<int> c;
    vector<int> ans(q, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1];
        c.push_back(a[i][0] + a[i][1]);
        c.push_back(a[i][1] - a[i][0]);
    }
    for (int i = 0; i < q; i++) {
        cin >> b[i][0] >> b[i][1];
        c.push_back(b[i][0]);
        c.push_back(b[i][1]);
    }
    c.push_back(-1e18);
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    int m = c.size();

    sort(a.begin(), a.end(), [](const array<int, 2> &a, const array<int, 2> &b){
        return a[0] + a[1] < b[0] + b[1];
    });
    
    vector<array<int, 4>> L;
    for (auto [x, y]: a) {
        int k2 = x + y, k1 = y - x;
        k2 = lower_bound(c.begin(), c.end(), k2) - c.begin();
        k1 = lower_bound(c.begin(), c.end(), k1) - c.begin();
        L.push_back({k2, k1, -2, 0});
    }
    
    for (int i = 0; i < q; i++) {
        int k2 = b[i][1], k1 = b[i][0];
        k2 = lower_bound(c.begin(), c.end(), k2) - c.begin();
        k1 = lower_bound(c.begin(), c.end(), k1) - c.begin();
        L.push_back({k2, k1, 1, i});
    }
    
    sort(L.begin(), L.end(), [](const array<int, 4> &a, const array<int, 4> &b){
        if (a[0] == b[0]) return a[2] > b[2];
        return a[0] < b[0];
    });
    
    vector<int> tr(m << 2);
    
    auto update = [&](auto &self, int l, int r, int x, int p) {
        if (l == r) {
            tr[p]++;
            return;
        }
        int mid = l + r >> 1;
        if (x <= mid) self(self, l, mid, x, p << 1);
        else self(self, mid + 1, r, x, p << 1 | 1);
        tr[p] = tr[p << 1] + tr[p << 1 | 1];
    };

    auto query = [&](auto &self, int l, int r, int ql, int qr, int p) {
        if (ql <= l && qr >= r) return tr[p];
        int mid = l + r >> 1, ans = 0;
        if (ql <= mid) ans += self(self, l, mid, ql, qr, p << 1);
        if (qr > mid) ans += self(self, mid + 1, r, ql, qr, p << 1 | 1);
        return ans;
    };
    
    for (auto[k2, k1, op, idx]: L) {
        if (op == -2) update(update, 1, m, k1, 1);
        else ans[idx] += query(query, 1, m, 1, max(1ll, k1 - 1), 1);
    }
    
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
    
    return 0;
}