莫队怎么做三维偏序？

众所周知，三维偏序的一般做法是 CDQ 分治，复杂度是两只 \log 的。

但是我们想要一个根号的做法。（根号信仰！）

目前根号做法有 KDT 和分块。然而 KDT 常数巨大，分块太困难了。这里介绍一种简单的莫队做法。

我们知道莫队是可以轻松做在线二维数点的。

考虑怎么将离线三维数点转化为在线二维数点。你可以将 a_i 作为时间、b_i 作为序列、c_i 作为值。带修莫队套值域分块可以轻松做到 O(n \sqrt n)。

但是这样做是假的。为什么？因为你一个位置可能会有很多值，这样莫队移动指针的复杂度就不是 O(1) 的，很容易就会被卡掉。

怎么办呢？可以把 b_i 离散化成一个排列，例如：

<-- 1 1 4 5 1 4
--> 1 2 4 6 3 5

形式化的：

那么我们修改的时候在对应位置修改，查询的时候查询最大与原序列值相等的位置。这样做就是对的！

我们发现这个带修莫队其实完全没必要。你可以对 a_i 和 b_i 都进行一次这样的离散化，然后像二维莫队那样维护两个指针就可以了。

你甚至可以把 c_i 也离散化，但是这样复杂度就是 n^{5/3} 的。

这个做法可以轻松推广到高维，复杂度和 KDT 应该是一样的，但是比 KDT 快多了。

三维偏序的代码：

https://www.luogu.com.cn/record/189289543

#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 5, K = 2e5 + 5, B1 = 1000, B2 = 300;
int n, k, a[N], b[N], c[N], a0[N], b0[N], la[K], ra[K], lb[K], rb[K], ab[N], ba[N], ac[N], bc[N],
    bel[K], val[K], sum[N], ans[N];
struct query {
    int a, b, c;
    inline bool operator<(const query &r) {
        if (bel[a] != bel[r.a]) return bel[a] < bel[r.a];
        return bel[a] & 1 ? b < r.b : b > r.b;
    }
} q[N];
inline void insert(int x) { ++val[x], ++sum[bel[x]]; }
inline void remove(int x) { --val[x], --sum[bel[x]]; }
inline int query(int x) {
    int ret = 0;
    for (int i = 1; i <= bel[x] - 1; i++) ret += sum[i];
    for (int i = x; bel[i] == bel[x]; i--) ret += val[i];
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i];
    for (int i = 1; i <= n; i++) a0[i] = a[i], b0[i] = b[i];
    sort(a0 + 1, a0 + n + 1);
    sort(b0 + 1, b0 + n + 1);
    for (int i = 1, j = 1; i <= n; i = ++j) {
        la[a0[i]] = ra[a0[i]] = i;
        while (a0[j + 1] == a0[i]) ++j, ++ra[a0[i]];
    }
    for (int i = 1, j = 1; i <= n; i = ++j) {
        lb[b0[i]] = rb[b0[i]] = i;
        while (b0[j + 1] == b0[i]) ++j, ++rb[b0[i]];
    }
    for (int i = 1; i <= n; i++) q[i] = {ra[a[i]], rb[b[i]], c[i]};
    for (int i = 1; i <= n; i++) {
        int x = la[a[i]]++, y = lb[b[i]]++;
        ab[x] = y, ba[y] = x, ac[x] = bc[y] = c[i];
    }
    for (int i = 1; i <= n; i++) bel[i] = i / B1;
    sort(q + 1, q + n + 1);
    for (int i = 1; i <= k; i++) bel[i] = (i - 1) / B2 + 1;
    for (int i = 1, a = 0, b = 0; i <= n; i++) {
        while (a < q[i].a)
            if (ab[++a] <= b) insert(ac[a]);
        while (a > q[i].a)
            if (ab[a--] <= b) remove(ac[a + 1]);
        while (b < q[i].b)
            if (ba[++b] <= a) insert(bc[b]);
        while (b > q[i].b)
            if (ba[b--] <= a) remove(bc[b + 1]);
        ++ans[query(q[i].c) - 1];
    }
    for (int i = 0; i < n; i++) cout << ans[i] << '\n';
}