bzoj1935: [Shoi2007]Tree 园丁的烦恼lowbit 离散化

链接

bzoj
最好不要去luogu，数据太水

思路

一个询问转化成四个矩阵，求起点\((0,0)到(x,y)\)的矩阵
离线处理，离散化掉y，x不用离散。
一行一行的求，每次处理完一行之后下一行的贡献直接叠加到当前。
用lowbit统计

错误

离散化小心点，是y-1不是y

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7, maxn = 5e5 + 1;
int read() {
    int x = 0, f = 1; char s = getchar();
    for (; s > '9' || s < '0'; s = getchar()) if (s == '-') f = -1;
    for (; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';
    return x * f;
}

int n, m, ans[N], x[N], y[N], X[N], Y[N];
pair<int, int> tree[N];
struct ask {
    int id, q, x, y;
    ask(int a = 0, int b = 0, int c = 0, int d = 0) {
        id = a, q = b, x = c, y = d;
        if (!x || !y) x = 0, y = 0;
    }
    bool operator < (const ask &b) const {
        return x < b.x;
    }
} Q[N<<2];

namespace BIT {
    int sum[N];
    inline int lowbit(int x) {
        return x & -x;
    }
    void add(int x) {
        for (int i = x; i <= maxn; i += lowbit(i))
            sum[i]++;
    }
    int query(int x) {
        int ans = 0;
        for (int i = x; i >= 1; i -= lowbit(i))
            ans += sum[i];
        return ans;
    }
}
int lsh[N<<3],len;

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; ++i) {
        tree[i].first = read() + 1, tree[i].second = read() + 1;
        lsh[++len] = tree[i].second;
    }
    int nd = 0;
    for (int i = 1, js = 0; i <= m; ++i) {
        int x = read() + 1, y = read() + 1, X = read() + 1, Y = read() + 1;
        lsh[++len] = Y, lsh[++len] = y - 1;
        if (X and Y)
        Q[++nd] = ask(i, 1, X, Y);
        if (X and (y - 1))
        Q[++nd] = ask(i, -1, X, y - 1);
        if ((x - 1) and Y)
        Q[++nd] = ask(i, -1, x - 1, Y);
        if ((x - 1) and (y - 1))
        Q[++nd] = ask(i, 1, x - 1, y - 1);
    }

    sort(lsh + 1, lsh + 1 + len);
    len = unique(lsh + 1, lsh + 1 + len) - lsh - 1;
    for (int i = 1; i <= n; ++i)
        tree[i].second = lower_bound(lsh + 1, lsh + 1 + len, tree[i].second) - lsh;
    for (int i = 1; i <= nd; ++i) {
        Q[i].y = lower_bound(lsh + 1, lsh + 1 + len, Q[i].y) - lsh;
    }
    
    sort(tree + 1, tree + 1 + n);
    sort(Q + 1, Q + 1 + nd);

    int js = 1;
    for (int i = 1; i <= nd; ++i) {
        while (tree[js].first <= Q[i].x && js <= n)
            BIT::add(tree[js].second),++js;
        ans[Q[i].id] += Q[i].q * BIT::query(Q[i].y);
    }

    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);

    return 0;
}