三维偏序

#include <cstdio>
#include <climits>

#include <algorithm>

#define LOG(FMT...) fprintf(stderr, FMT)
#define GET_CH(P, F) ((F) ? (P)->rs : (P)->ls)

using namespace std;

struct node {
    int x, cnt, rnd;
    node *ls, *rs;
};

struct data {
    int a, b, c;

    bool operator<(const data& x) const;
};

const int N = 100010;

int n;
int cnt[N], xb[N];
node *t[N];
data d[N];

int low_bit(int x);
void change(int b, int c);
int query(int b, int c);
node* create(int x);
void insert(node*& p, node* q);
int query(node* p, int x);
void rotate(node*& p, bool f);
void update(node* p);
int get_sz(node* p);

int main() {
    int ib, cur;
    {
        int ig;
        scanf("%d%d", &n, &ig);
    }
    for (int i = 1; i <= n; ++i)
        scanf("%d%d%d", &d[i].a, &d[i].b, &d[i].c);
    for (int i = 1; i <= n; ++i)
        xb[i] = d[i].b;
    sort(d + 1, d + n + 1);
    sort(xb + 1, xb + n + 1);
    for (int i = 1; i <= n;) {
        cur = i;
        do {
            ib = lower_bound(xb + 1, xb + n + 1, d[i].b) - xb;
            change(ib, d[i].c);
            ++i;
        } while (i <= n && d[i].a == d[i - 1].a);
        for (int j = cur; j < i; ++j) {
            ib = lower_bound(xb + 1, xb + n + 1, d[j].b) - xb;
            ++cnt[query(ib, d[j].c)];
        }
    }
    for (int i = 1; i <= n; ++i)
        printf("%d\n", cnt[i]);
    return 0;
}

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

bool data::operator<(const data& x) const {
    if (a == x.a) {
        if (b == x.b)
            return c < x.c;
        return b < x.b;
    }
    return a < x.a;
}

inline void change(int b, int c) {
    for (; b <= n; b += low_bit(b))
        insert(t[b], create(c));
}

inline int query(int b, int c) {
    int ret = 0;
    for (; b; b -= low_bit(b))
        ret += query(t[b], c);
    return ret;
}

inline int query(node* p, int x) {
    int ret = 0;
    while (p) {
        if (p->x <= x) {
            ret += get_sz(p->ls) + 1;
            p = p->rs;
        } else
            p = p->ls;
    }
    return ret;
}

inline int get_sz(node* p)
{ return p ? p->cnt : 0; }

inline node* create(int x) {
    static node pool[N << 5];
    static node* p = pool;
    ++p;
    p->x = x;
    p->cnt = 1;
    p->rnd = low_bit(p - pool);
    return p;
}

void insert(node*& p, node* q) {
    if (!p) {
        p = q;
        return;
    }
    if (p->x > q->x) {
        insert(p->ls, q);
        update(p);
        if (p->rnd < p->ls->rnd)
            rotate(p, 0);
    } else {
        insert(p->rs, q);
        update(p);
        if (p->rnd < p->rs->rnd)
            rotate(p, 1);
    }
}

inline void rotate(node*& p, bool f) {
    node *son = GET_CH(p, f), *pson = GET_CH(son, !f);
    GET_CH(son, !f) = p;
    GET_CH(p, f) = pson;
    update(p);
    p = son;
    update(p);
}

inline void update(node* p)
{ p->cnt = get_sz(p->ls) + get_sz(p->rs) + 1; }