学步园

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000001;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x*f;
}
const int N = 2000001;
int n, m, cnt, que, x[N], y[N], py[N], a[N], b[N], c[N], d[N], t[N << 1], ans[N][5];

struct data {
    int x, y, id, f;
} q[N << 1];

inline bool operator<(data a, data b) {
    return a.x < b.x || (a.x == b.x && a.f < b.f);
}

inline void add(int x, int y) {
    for (int i = x; i <= cnt; i += i & (-i))
        t[i] += y;
}

inline int query(int x) {
    int res = 0;
    for (int i = x; i; i -= i & (-i))
        res += t[i];
    return res;
}

inline int find(int x) {
    int l = 1, r = cnt;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (py[mid] == x)return mid;
        else if (py[mid] < x)l = mid + 1;
        else r = mid - 1;
    }
}

int main() {
    n = read();
    m = read();
    for (int i = 1; i <= n; i++) {
        x[i] = read();
        y[i] = read();
        py[++cnt] = y[i];
    }
    for (int i = 1; i <= m; i++) {
        a[i] = read();
        b[i] = read();
        c[i] = read();
        d[i] = read();
        py[++cnt] = b[i];
        py[++cnt] = d[i];
    }
    sort(py + 1, py + cnt + 1);
    cnt = unique(py + 1, py + cnt + 1) - py - 1;
    for (int i = 1; i <= n; i++) {
        y[i] = find(y[i]);
        q[++que] = (data){x[i], y[i], 0, 0};
    }
    for (int i = 1; i <= m; i++) {
        b[i] = find(b[i]);
        d[i] = find(d[i]);
        q[++que] = (data){c[i], d[i], i, 1};
        q[++que] = (data){a[i] - 1, d[i], i, 2};
        q[++que] = (data){c[i], b[i] - 1, i, 3};
        q[++que] = (data){a[i] - 1, b[i] - 1, i, 4};
    }
    sort(q + 1, q + que + 1);
    for (int i = 1; i <= que; i++) {
        if (!q[i].f)add(q[i].y, 1);
        else ans[q[i].id][q[i].f] = query(q[i].y);
    }
    for (int i = 1; i <= m; i++)
        printf("%d\n", ans[i][1] + ans[i][4] - ans[i][2] - ans[i][3]);
    return 0;
}