## [ZeroJudge c571. 三維偏序問題](https://zerojudge.tw/ShowProblem?problemid=c571)
CDQ分治題，但我不要CDQ分治。
雖然CDQ分治的時間複雜度為$O(n \log^2 n)$，空間是好好的$O(n)$，但我不擅長分治。
所以我決定用動態開點線段樹直接模擬，時間也是$O(n \log^2 n)$，而空間則是$O(n \log^2 n)$。
~~之後我發現我被卡常了，所以我就用快讀快寫硬卡過了ww~~
我的動態開點線段樹是寫偽指標，~~但是是指標型的偽指標~~，扣當參考就好，很醜。
:::spoiler code:

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include <bits/stdc++.h>
#include <unistd.h>
#define F first
#define S second
#define lowbit(x) ((x) & -(x))
using namespace std;
using i64 = long long;
using u32 = uint32_t;
using p2i = pair<int, int>;
using p2l = pair<i64, i64>;

inline namespace fake_pointer_impl {

constexpr u32 blk_lg = 12;
constexpr u32 blk_sz = 1 << blk_lg;
constexpr u32 blk_mod = blk_sz - 1;

template <typename Tp>
struct fake_pointer {
    static inline vector<Tp*> pool;
    static inline u32 cnt = 0;

    int32_t id;
    fake_pointer() :id(-1) {}
    fake_pointer(nullptr_t) :id(-1) {}
    fake_pointer(const fake_pointer&) = default;
    fake_pointer(fake_pointer&&) = default;

    inline fake_pointer&
    operator=(nullptr_t)
    { return (id = -1), *this; }
    inline fake_pointer&
    operator=(const fake_pointer&) = default;
    inline fake_pointer&
    operator=(fake_pointer&&) = default;

    inline Tp&
    operator*() const
    { return pool[id >> blk_lg][id & blk_mod]; }

    inline Tp*
    operator->() const
    { return &(this->operator*()); }

    explicit operator bool() const
    { return id >= 0; }

    operator Tp*() const
    { return (this->operator->()); }

    static inline fake_pointer
    single_alloc() {
        if (!(cnt & blk_mod)) pool.emplace_back(static_cast<Tp*>(::operator new(sizeof(Tp) * blk_sz)));
        return fake_pointer(cnt++);
    }
private:
    fake_pointer(int32_t _id) :id(_id) {}
};

};

inline namespace dont_open_segtree_impl {

struct dont_open_segtree_node {
    u32 cnt;
    fake_pointer<dont_open_segtree_node> p_l, p_r;
    dont_open_segtree_node() :cnt(0), p_l(), p_r() {}
};

struct dont_open_segtree {
    u32 n;
    fake_pointer<dont_open_segtree_node> root;
    using node_pointer = fake_pointer<dont_open_segtree_node>;
    dont_open_segtree() :n(0), root() {}
    dont_open_segtree(u32 _n) :n(_n), root() {}

    inline void
    modify(u32 pos, u32 val) {
        return modify(0, n, pos, val, root);
    }

    inline u32
    query(u32 ql, u32 qr) {
        return query(0, n, ql, qr, root);
    }

private:
    inline void
    modify(u32 l, u32 r, u32 pos, u32 val, node_pointer& p) {
        if (!p) {
            p = node_pointer::single_alloc();
            ::new(static_cast<dont_open_segtree_node*>(p)) dont_open_segtree_node();
        }
        p->cnt += val;
        if (r - l == 1) return;
        u32 m = (l + r) >> 1;
        return ((pos < m) ? modify(l, m, pos, val, p->p_l) : modify(m, r, pos, val, p->p_r));
    }

    inline u32
    query(u32 l, u32 r, u32 ql, u32 qr, node_pointer p) {
        if (!p) return 0;
        if (ql <= l && r <= qr) return p->cnt;
        u32 m = (l + r) >> 1;
        if (qr <= m) return query(l, m, ql, qr, p->p_l);
        if (ql >= m) return query(m, r, ql, qr, p->p_r);
        return query(l, m, ql, qr, p->p_l) + query(m, r, ql, qr, p->p_r);
    }
};

struct dont_open_segtree_2D_node {
    dont_open_segtree seg;
    fake_pointer<dont_open_segtree_2D_node> p_l, p_r;
    dont_open_segtree_2D_node() = default;
    dont_open_segtree_2D_node(u32 _n) :seg(_n), p_l(), p_r() {}
};

struct dont_open_segtree_2D {
    u32 n;
    fake_pointer<dont_open_segtree_2D_node> root;
    using node_pointer = fake_pointer<dont_open_segtree_2D_node>;
    dont_open_segtree_2D(u32 _n) :n(_n), root() {}

    inline void
    modify(u32 pos_x, u32 pos_y, u32 val) {
        return modify(0, n, pos_x, pos_y, val, root);
    }

    inline u32
    query(u32 ql_x, u32 qr_x, u32 ql_y, u32 qr_y) {
        return query(0, n, ql_x, qr_x, ql_y, qr_y, root);
    }

private:
    inline void
    modify(u32 l, u32 r, u32 pos_x, u32 pos_y, u32 val, node_pointer& p) {
        if (!p) {
            p = node_pointer::single_alloc();
            ::new(static_cast<dont_open_segtree_2D_node*>(p)) dont_open_segtree_2D_node(n);
        }
        (p->seg).modify(pos_y, val);
        if (r - l == 1) return;
        u32 m = (l + r) >> 1;
        return ((pos_x < m) ? modify(l, m, pos_x, pos_y, val, p->p_l) : modify(m, r, pos_x, pos_y, val, p->p_r));
    }

    inline u32
    query(u32 l, u32 r, u32 ql_x, u32 qr_x, u32 ql_y, u32 qr_y, node_pointer p) {
        if (!p) return 0;
        if (ql_x <= l && r <= qr_x) return (p->seg).query(ql_y, qr_y);
        u32 m = (l + r) >> 1;
        if (qr_x <= m) return query(l, m, ql_x, qr_x, ql_y, qr_y, p->p_l);
        if (ql_x >= m) return query(m, r, ql_x, qr_x, ql_y, qr_y, p->p_r);
        return query(l, m, ql_x, qr_x, ql_y, qr_y, p->p_l) + query(m, r, ql_x, qr_x, ql_y, qr_y, p->p_r);
    }
};

};

inline namespace fastIO {

constexpr u32 Ibuf_size = 1 << 17;

struct In {
    char Ibuf[Ibuf_size], *Il, *Ir, Ic;
    In() :Il(Ibuf), Ir(Ibuf), Ic() {}

    inline void
    load() {
        Ir = ((Il = Ibuf) + fread(Ibuf, 1, Ibuf_size, stdin));
    }

#define get_char() (((Il == Ir) && (load(), (Il == Ir))) ? -1 : *Il++)

    inline In&
    operator>>(u32& __x) {
        while (!isdigit(Ic = get_char()));
        __x = Ic & 15;
        while (isdigit(Ic = get_char()))
            (__x *= 10) += Ic & 15;
        return *this;
    }
} static cIn;

constexpr u32 Obuf_size = 1 << 17;

struct Out {
    char Obuf[Obuf_size], *Ol, *Or;
    Out() :Ol(Obuf), Or(Obuf + Obuf_size) {}
    ~Out() { flush(); }

    inline void
    flush() {
        write(1, Obuf, Ol - Obuf);
        Ol = Obuf;
    }

    inline Out&
    operator<<(char __c) {
        if (Ol == Or) flush();
        *Ol++ = __c;
        return *this;
    }

    inline Out&
    operator<<(u32 __x) {
        static char num_buf[8];
        static u32 len;
        len = 0;
        do {
            num_buf[len++] = (__x % 10) ^ 48;
        } while (__x /= 10);
        if (Ol + len >= Or) flush();
        while (len--) *Ol++ = num_buf[len];
        return *this;
    }
} static cOut;

};

#define cin cIn
#define cout cOut

int main() {
    u32 n; cin >> n;
    vector<tuple<u32, u32, u32>> v(n);
    vector<u32> ans(n, 0), idx(n);
    iota(idx.begin(), idx.end(), 0);
    dont_open_segtree_2D sgt(n);
    for (int i = 0; i < n; i++) {
        cin >> get<0>(v[i]) >> get<1>(v[i]) >> get<2>(v[i]);
    }
    sort(idx.begin(), idx.end(), [&v](const auto& a, const auto& b) -> bool {
        return (get<0>(v[a]) > get<0>(v[b])) || ((get<0>(v[a]) == get<0>(v[b])) && (get<1>(v[a]) < get<1>(v[b])));
    });
    for (auto i : idx) {
        ans[i] = sgt.query(get<1>(v[i]), n, get<2>(v[i]), n);
        sgt.modify(get<1>(v[i]) - 1, get<2>(v[i]) - 1, 1);
    }
    for (auto i : ans) cout << i << '\n';
    return 0;
}

:::

:::spoiler upd : CDQ分治 AC code:

#include <bits/stdc++.h>
using namespace std;

pair<int, pair<int, int>> points[100000];

int id[100000], ans[100000], fwt[100002], N;

void modify(int x, int val) {
    for (; x <= N + 1; x += (x & -x)) fwt[x] += val;
}

int query(int cnt) {
    int ret = 0;
    for (; cnt; cnt -= (cnt & -cnt)) ret += fwt[cnt];
    return ret;
}

bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.first > b.first || (a.first == b.first && a.second < b.second);
}

void cdq(int l, int r) {
    static int tmp[100000];
    if (r - l == 1) return;
    int m = (l + r) >> 1;
    cdq(l, m), cdq(m, r);
    int i = m - 1, j = r - 1, idx = r;
    for (; i >= l || j >= m; ) {
        if (i < l) {
            tmp[--idx] = id[j];
            modify(points[id[j]].second.second, 1);
            --j;
            continue;
        }
        if (j < m) {
            tmp[--idx] = id[i];
            ans[id[i]] += query(N) - query(points[id[i]].second.second);
            --i;
            continue;
        }
        if (cmp(points[id[i]].second, points[id[j]].second)) {
            tmp[--idx] = id[i];
            ans[id[i]] += query(N) - query(points[id[i]].second.second);
            --i;
            continue;
        }
        else {
            tmp[--idx] = id[j];
            modify(points[id[j]].second.second, 1);
            --j;
            continue;
        }
    }
    for (idx = r; idx-- > m; ) {
        modify(points[id[idx]].second.second, -1);
    }
    copy(tmp + l, tmp + r, id + l);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> points[i].first >> points[i].second.first >> points[i].second.second;
        id[i] = i;
    }
    sort(id, id + N, [&](const auto a, const auto b) -> bool {
        return points[a].first < points[b].first || (points[a].first == points[b].first && points[a].second > points[b].second);
    });
    cdq(0, N);
    for (int i = 0; i < N; i++) cout << ans[i] << '\n';
    return 0;
}

:::