2log 时间低空间在线动态二维数点

· · 题解

这是一个在线动态二维数点问题。

追忆一下不在线怎么做，是 CDQ 分治后转成离线静态二维数点。

但是现在需要在线，考虑一个东西：二进制分组。

假设当前有 s 个点，那么考虑 s 的二进制分解，若第 k 位为 1，就分一个大小为 2^k 的组，那么所有点会被我们分成 O(\log n) 组。

然后新加入一个点，就会像二进制进位一样，产生组的合并，一个点最多参与 O(\log n) 次合并，所有合并出来的组的大小总和为 O(n \log n)。

每个组都用一个数据结构维护，然后查询这 O(\log n) 个组即可。

这样在线动态二维数点问题就被转化为了在线静态二维数点问题。注意一下这里还是在线的。

一般来说我们会使用持久化线段树来解决这个问题，但是持久化线段树的节点数高达 O(n \log n) 个，还需要记录左右儿子，空间超过了 40MB，不可接受。

考虑冷门科技 Wavelet Matrix 小波矩阵，这个有点复杂，这里不讲述原理，可以看 staring 的文章。Wavelet Matrix 如其名，整个数据结构被排列成了一个矩阵，不需要记录左右儿子，结构紧凑，例如区间 kth 问题能够用 Wavelet Matrix 做到线性空间。

但是怎么用 Wavelet Matrix 求矩形和呢？考虑把所有点按照 x 坐标排序，那么我们只需求一个 \sum_{i=l}^{r}[a_y \le R] a_w 状物。这个用 Wavelet Matrix 是容易求的。

然后 Wavelet Matrix 每一行需要存一个前缀权值和数组，这个优化不掉，但是只有 16MB，在此题中可以接受，另外 Wavelet Matrix 的结构里还需要存一个前缀 1 个数的数组，这个是同线性空间区间 kth 的经典技巧，用手写 bitset 缩掉即可。

然后是一些常数优化，比如大小不超过 128 的组直接暴力。

时间复杂度 O(n \log^2 n)，空间复杂度 O(n \log n)。

本题中的点数不是很满，我的实现是只用了 11.84MB。

const int N = 2e5 + 5;
const int B = 128;
struct Point {
    int x, y, w;
    bool operator < (const Point & A) {
        return x < A.x;
    }
};
struct Bitset {
    int n;
    VC<ull> a; VI c;
    Bitset(int sz = 0) {
        n = (sz >> 6) + 2;
        a = VC<ull>(n);
        c = VI(n);
    }
    inline void set(int u) {
        a[u >> 6] |= 1ull << (u & 63);
    }
    void build() {
        FOR(i, 1, n - 1) c[i] = c[i - 1] + popcountll(a[i - 1]);
    }
    inline int popcount(int r) {
        return c[r >> 6] + popcountll(a[r >> 6] & ((1ull << (r & 63)) - 1));
    }
};
struct Wavelet {
    int n, m, lim;
    VC<Point> a, b;
    VI bl, br, pr;
    VI s[19]; int p[19];
    Bitset c[19];
    Wavelet() {
        n = 0;
    }
    void build() {
        n = SZ(a); lim = __lg(n);
        if(n <= B) return;
        for(auto h : a) bl.pb(h.x), br.pb(h.y);
        UNI(bl); UNI(br);
        for(auto h : a) {
            int x = LWB(bl, h.x) + 1;
            int y = LWB(br, h.y);
            b.pb({x, y, h.w});
        }
        m = SZ(b); sort(ALL(b));
        pr = VI(SZ(bl) + 1); pr[0] = - 1;
        REP(i, m) pr[b[i].x] = i;
        ROF(j, lim, 0) {
            s[j] = VI(m + 1);
            c[j] = Bitset(m);
            REP(i, m) {
                s[j][i + 1] = s[j][i];
                if(b[i].y >> j & 1) c[j].set(i);
                else s[j][i + 1] += b[i].w;
            }
            c[j].build();
            p[j] = stable_partition(ALL(b), [&] (Point h) { return ! (h.y >> j & 1); }) - BG(b);
        }
    }
    int query(int l, int r, int x) {
        int res = 0;
        ROF(j, lim, 0) {
            int L = c[j].popcount(l);
            int R = c[j].popcount(r + 1);
            if(x >> j & 1) {
                res += s[j][r + 1] - s[j][l];
                l = p[j] + L;
                r = p[j] + R - 1;
            }
            else {
                l -= L;
                r -= R;
            }
        }
        return res;
    }
    int query(int U, int D, int L, int R) {
        if(n <= B) {
            int res = 0;
            for(auto h : a) if(U <= h.x && h.x <= D && L <= h.y && h.y <= R)
                res += h.w;
            return res;
        }
        else {
            U = pr[LWB(bl, U)] + 1;
            D = pr[LWB(bl, D + 1)];
            L = LWB(br, L);
            R = LWB(br, R + 1);
            return query(U, D, R) - query(U, D, L);
        }
    }
} F[19];
void insert(Wavelet & W, int u) {
    if(F[u].n) {
        for(auto x : F[u].a) W.a.pb(x);
        F[u] = Wavelet();
        insert(W, u + 1);
    }
    else {
        F[u] = W;
        F[u].build();
    }
}
void solve() {
    INT(n);
    int lst = 0;
    while(1) {
        INT(o);
        if(o == 1) {
            INT(x, y, w);
            x ^= lst; y ^= lst; w ^= lst;
            Wavelet W;
            W.a.pb({x, y, w});
            insert(W, 0);
        }
        if(o == 2) {
            INT(U, L, D, R);
            U ^= lst; D ^= lst; L ^= lst; R ^= lst;
            int ans = 0;
            REP(i, 19) if(F[i].n) ans += F[i].query(U, D, L, R);
            print(lst = ans);
        }
        if(o == 3) {
            break;
        }
    }
}