题解：P10814 【模板】离线二维数点

Loser_Syx · 2024-07-29 07:38:11 · 题解

我们考虑一个 [l,r] 的答案，可以想到用 [1,r] 的答案减去 [1,l-1] 的答案，于是可以直接差分为两段计算。

考虑对每个 [1,k] 计算答案，我们将 k 排序后发现数组是有序的，可以直接 1\sim n 加点，现在就是要维护 [1,k] 中存在多少个元素 \leq x，权值树状数组可以做到，故复杂度 O(n \log n)。

const int N = 2e6 + 19;
struct node {
    int k, id, x, val;
    bool operator < (const node &a) const {
        return k < a.k;
    }
} q[N << 1];
int a[N], cnt, ans[N];
struct BinaryTree {
    int t[N];
    void add(int x) {
        while (x < N) {
            t[x]++;
            x += lowbit(x);
        }
    }
    int query(int x) {
        int res = 0;
        while (x) {
            res += t[x];
            x -= lowbit(x);
        }
        return res;
    }
} bit;
signed main() {
    int n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    for (int i = 1; i <= m; ++i) {
        int l, r, x; read(l, r, x);
        q[++cnt] = {l-1, i, x, -1};
        q[++cnt] = {r, i, x, 1};
    }
    sort(q + 1, q + 1 + cnt);
    for (int i = 1, j = 1; i <= cnt; ++i) {
        for (; j <= q[i].k; ++j) bit.add(a[j]);
        ans[q[i].id] += q[i].val * bit.query(q[i].x);
    }
    for (int i = 1; i <= m; ++i) write(ans[i]);
    return 0;
}