P2163 [SHOI2007] 園丁的煩惱 - 洛谷 | 計(jì)算機(jī)科學(xué)教育新生態(tài) (luogu.com.cn)

這個(gè)是二維數(shù)點(diǎn)的板子題，二維數(shù)點(diǎn)這一類題目就是上面的題所描述的，我們用樹(shù)狀數(shù)組 + 離散化來(lái)解決這個(gè)問(wèn)題。

這里就不解釋了，記錄此篇博文的目的主要就是提醒自己曾經(jīng)學(xué)過(guò)這個(gè)，看看代碼，方便回憶起來(lái)。

這題其實(shí)不用離散化，離散化會(huì) T，開(kāi) O2 才能過(guò)。

//The code was written by yifan, and yifan is neutral!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define bug puts("NOIP rp ++!");
typedef pair<int, int> pii;
#define lowbit(x) (x & (-x))

template<typename T>
inline T read() {
    T x = 0;
    bool fg = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        fg |= (ch == '-');
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return fg ? ~x + 1 : x;
}

const int N = 1e6 + 5;

int n, m, lim;
ll t[N << 3];
ll ans[N];
pii v[N];
vector<int> s;

struct vt {
    int x, y;
} V[N];

struct ASK {
    int xl, yl, xr, yr;
} Ask[N << 2];

struct Query {
    int x, y, opt, id;
} ask[N << 2];

void add(int x, int v) {
    while (x <= lim) {
        t[x] += v;
        x += lowbit(x);
    }
}

ll query(int x) {
    ll ans = 0;
    while (x) {
        ans += t[x];
        x -= lowbit(x);
    }
    return ans;
}

int main() {
    n = read<int>(), m = read<int>();
    s.emplace_back(-100);
    for (int i = 1; i <= n; ++ i) {
        int x = read<int>(), y = read<int>();
        V[i] = vt{x, y};
        s.emplace_back(x), s.emplace_back(y);
    }
    for (int i = 1; i <= m; ++ i) {
        int xl = read<int>(), yl = read<int>(), xr = read<int>(), yr = read<int>();
        Ask[i] = ASK{xl, yl, xr, yr};
        s.emplace_back(xl), s.emplace_back(yl);
        s.emplace_back(xr), s.emplace_back(yr);
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    for (int i = 1; i <= n; ++ i) {
        int x = lower_bound(s.begin(), s.end(), V[i].x) - s.begin() + 1;
        int y = lower_bound(s.begin(), s.end(), V[i].y) - s.begin() + 1;
        v[i] = {x, y};
        // cout << x << ' ' << y << '\n';
    }
    for (int i = 1; i <= m; ++ i) {
        int xl = lower_bound(s.begin(), s.end(), Ask[i].xl) - s.begin() + 1;
        int yl = lower_bound(s.begin(), s.end(), Ask[i].yl) - s.begin() + 1;
        int xr = lower_bound(s.begin(), s.end(), Ask[i].xr) - s.begin() + 1;
        int yr = lower_bound(s.begin(), s.end(), Ask[i].yr) - s.begin() + 1;
        ask[i] = Query{xl - 1, yl - 1, 1, i};
        ask[i + m] = Query{xl - 1, yr, -1, i};
        ask[i + 2 * m] = Query{xr, yl - 1, -1, i};
        ask[i + 3 * m] = Query{xr, yr, 1, i};
    }
    sort(v + 1, v + n + 1);
    sort(ask + 1, ask + 4 * m + 1, [](Query a, Query b) -> bool {
        return a.x < b.x;
    });
    int cur = 1;
    lim = s.size();
    for (int i = 1; i <= 4 * m; ++ i) {
        Query it = ask[i];
        while (v[cur].first <= it.x && cur <= n) {
            add(v[cur].second, 1);
            ++ cur;
        }
        ans[it.id] += it.opt * query(it.y);
    }
    for (int i = 1; i <= m; ++ i) {
        cout << ans[i] << '\n';
    }
    return 0;
}