二维动态树状数组做法(性质–半离线预处理)

三维偏序的问题， 为什么都是cdq分治的题解，没有2D数据结构查询的做法呢？ 作为一个没脑子不会推cdq的人，感觉还是应该补充一个这种更易懂的做法。

首先我们可以想到，对于我们常见的kd-树，单次查询为 $O(\sqrt n)$，在本题只有1s的时限内，必然是跑不动的。所以我们需要回到二维更常用的树套树上。

思路介绍–如何使用在线的2D查询解决本题

在介绍数据结构的优化之前，我们先说一下这种题拿树套树等二维数据结构要怎么做吧。

我们要找到所有满足条件的 $a_j \le a_i, b_j\le b_i, c_j \le c_i$，那么第一个维度 $a$ 我们可以直接从小到大进行排序。

接下来我们按照 $a$ 维度从小到大进行遍历，每次在二维空间中，查询与自己不完全相同的，满足 $(b_j\le b_i, c_j\le c_i)$ 的个数 $g(i)$(由于 $a$ 维度已经从小到大排序，所以必然是成立的)，与自己三维完全相同的个数为 $h(i)$ ，那么 $f(i) = g(i) + h(i)$ ，此时答案为 $f(i)$ 的个数要多 $h(i) + 1$ 个。

这样我们便可以得到所有的答案。排序为 $O(n\log n)$, 查询总时间为 $O(n\log^2 n)$。

数据结构介绍–如何选取合适的数据结构

其中插入、查询全部操作强制在线的操作可以见我之前的一篇题解，但是这种强制在线，会导致空间与时间的常数巨大，虽然量纲没错，但是绝对过不去。

所以我们可以采用更折中的一种做法，即在事先知道哪些位置需要插入点之后，对所有点进行离散化，在统一建好的树上，再逐一加入点权，以及进行查询。这样可以大量的减少时间和空间的开销。

再考虑到本题的点权之间是进行加法求和，树状数组可以表示前缀加和，且拥有比线段树更优的常数，所以我们可以考虑采用 二维动态树状数组，先模拟一次运算过程（不进行实际运算）加点，所有点加入之后统一建树，再遍历一次进行实际的计算，加入点权，二维区间查询即可。

实际上这种做法在优化开满之后，时间与空间都只是略逊于cdq做法而已，就算是极致的毒瘤也没法为了只允许cdq分治过而不让该做法通过。

通过代码

去掉了头文件和快读快写，关键是理解二维数据结构的应用方法，以及本题的算法流程，希望各位可以自己实现一遍~

// 2D Fenwick Range Tree from Nyaan
// bit ... data_structure_type
// S ... size_type
// T ... value_type

template <typename S, typename T>
struct FenwickRangeTree {
    struct BIT {
        int N;
        vector<T> data;

        BIT() = default;
        BIT(int size) {
            init(size);
        }

        void init(int size) {
            N = size;
            data.assign(N + 1, 0);
        }

        // data[k] += x
        void add(int k, T x) {
            for (++k; k <= N; k += k & -k)
                data[k] += x;
        }

        T sum(int k) const {
            if (k <= 0)
                return T();

            T ret = T();

            for (; k; k -= k & -k)
                ret += data[k];

            return ret;
        }

        inline T sum(int l, int r) const {
            return sum(r) - sum(l);
        }
    };

    using P = pair<S, S>;
    S N, M;
    vector<BIT> bit;
    vector<vector<S>> ys;
    vector<P> ps;

    FenwickRangeTree() = default;

    void add_point(S x, S y) {
        ps.push_back(make_pair(x, y));
    }

    void build() {
        sort(begin(ps), end(ps));
        ps.erase(unique(begin(ps), end(ps)), end(ps));
        N = ps.size();
        bit.resize(N + 1);
        ys.resize(N + 1);

        for (int i = 0; i <= N; ++i) {
            for (int j = i + 1; j <= N; j += j & -j)
                ys[j].push_back(ps[i].second);

            sort(begin(ys[i]), end(ys[i]));
            ys[i].erase(unique(begin(ys[i]), end(ys[i])), end(ys[i]));
            bit[i].init(ys[i].size());
        }
    }

    int id(S x) const {
        return lower_bound(
                   begin(ps), end(ps), make_pair(x, S()),
        [](const P & a, const P & b) {
            return a.first < b.first;
        }) -
        begin(ps);
    }

    int id(int i, S y) const {
        return lower_bound(begin(ys[i]), end(ys[i]), y) - begin(ys[i]);
    }

    void add(S x, S y, T a) {
        int i = lower_bound(begin(ps), end(ps), make_pair(x, y)) - begin(ps);
        assert(ps[i] == make_pair(x, y));

        for (++i; i <= N; i += i & -i)
            bit[i].add(id(i, y), a);
    }

    T sum(S x, S y) const {
        T ret = T();

        for (int a = id(x); a; a -= a & -a)
            ret += bit[a].sum(id(a, y));

        return ret;
    }
    // x : [xl, xr)  y : [yl, yr)
    T sum(S xl, S yl, S xr, S yr) const {
        return sum(xr, yr) - sum(xl, yr) - sum(xr, yl) + sum(xl, yl);
    }
};
struct item {
    int a, b, c;
    bool operator == (const item &o) const {
        return a == o.a && b == o.b && c == o.c;
    }
    bool operator <(const item &o) const {
        if (a != o.a)
            return a < o.a;
        else if (b != o.b)
            return b < o.b;
        else
            return c < o.c;
    }
} a[100010];
FenwickRangeTree<int, int> bit;
int ans[100010], cnt[100010];// cnt 记录和当前自己属性值完全一样的个数(除自身之外)
int main() {
    int n = rd(), k = rd();

    for (int i = 0; i < n; ++i)
        a[i].a = rd(), a[i].b = rd(), a[i].c = rd();

    sort(a, a + n);// 按照 a 维度 从小到大排序

    //第一遍过程 : 仅是模拟验算，只把该加的点加进去
    for (int i = 0; i < n; ++i) {
        if (i != (n - 1) && a[i] == a[i + 1])
            continue;
        else
            bit.add_point(a[i].b, a[i].c);
    }
    //得到所有点之后，二维动态树状数组统一建树，这也就是所谓的半离线方法(预处理离线，而非全程离线)
    bit.build();

    for (int i = 0; i < n; ++i) {
        // 如果和后一个相同，则该点不做计算，并将自己的重复个数传递给后面
        if (i != (n - 1) && a[i] == a[i + 1])
            cnt[i + 1] = cnt[i] + 1;
        else {
            // 查询与自己不一样且满足条件的 g(i) 与和自己完全一样的 h(i) 对应的f(i)=g(i)+h(i)
            int tmp = bit.sum(0, 0, a[i].b + 1, a[i].c + 1) + cnt[i];
            // 对答案 f(i) 个数的贡献为 h(i) + 1
            ans[tmp] += cnt[i] + 1;
            // 这部分计算完毕之后，所有 h(i)+1 个重合的点加进树中，将 h(i)+1视为对该点的点权贡献
            bit.add(a[i].b, a[i].c, cnt[i] + 1);
        }
    }

    for (int i = 0; i < n; ++i)
        wr(ans[i]), putchar('\n');
}