SHOI2007 Tree

#include <cstdio>

#include <algorithm>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

struct node {
    int x, y, id, type;

    bool operator<(const node& x) const {
        if (y == x.y)
            return node::x < x.x;
        return y < x.y;
    }
};

const int N = 500010;

int n, m;

int a[N], px[N], ans[N];
node t[N * 5];

inline int low_bit(int x) { return x & -x; }
void change(int x);
int query(int x);

int main() {
#ifdef USE_CODE_RUNNER
    freopen("test.in", "r", stdin);
#endif

    int x1, x2, y1, y2, i1, i2, i3, i4, rep;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &t[i].x, &t[i].y);
        px[i] = t[i].x;
    }
    sort(px + 1, px + n + 1);
    for (int i = 1; i <= n; ++i)
        t[i].x = lower_bound(px + 1, px + n + 1, t[i].x) - px;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        i1 = i * 4 - 3 + n;
        i2 = i * 4 - 2 + n;
        i3 = i * 4 - 1 + n;
        i4 = i * 4 + n;
        t[i1].id = t[i2].id = t[i3].id = t[i4].id = i;
        t[i1].x = t[i3].x = lower_bound(px + 1, px + n + 1, x1) - px - 1;
        t[i2].x = t[i4].x = upper_bound(px + 1, px + n + 1, x2) - px - 1;
        t[i1].y = t[i2].y = y1 - 1;
        t[i3].y = t[i4].y = y2;
        t[i2].type = t[i3].type = -1;
        t[i1].type = t[i4].type = 1;
    }
    rep = n + m * 4;
    stable_sort(t + 1, t + rep + 1);
    for (int i = 1; i <= rep; ++i)
        if (!t[i].type)
            change(t[i].x);
        else
            ans[t[i].id] += t[i].type * query(t[i].x);
    for (int i = 1; i <= m; ++i)
        printf("%d\n", ans[i]);
    return 0;
}

inline void change(int x) {
    for (; x <= n; x += low_bit(x))
        ++a[x];
}

inline int query(int x) {
    int ret = 0;
    for (; x; x -= low_bit(x))
        ret += a[x];
    return ret;
}