题解：P14513 [NFLSPC #8] 追忆desuwa

· · 题解

\gdef\opt{\operatorname}

建议改为，【模板】小波矩阵（？？？。非常好题，使我的小波矩阵旋转。

首先发现这个查询形如求前驱，于是考虑 \opt{prev}(x)=\opt{kmin}(\opt{rank}(x+1)-1)。

注意到 \opt{rank},\opt{kmin} 都是 无权数点 问题，于是把修改 (l_i,r_i,v_i) 拆开，记 v_i 按 l_i 不降排序得到的序列为 a_i，v_i 按 r_i+1 不降排序得到的序列为 b_i。

对于一次查询 (x,y)，记 L=\sum_i [l_i \le x],R=\sum_i [r_i+1 \le x]，于是对 a[1,L],b[1,R] 进行查询，查询时 a_i 为 +1 的正贡献，b_i 为 -1 的负贡献。

于是现在问题的核心为：以最劣 O(n\log{V})-O(n) 的时空复杂度，回答在线静态 无权 二维数点问题。

阅读 P3834 【模板】可持久化线段树 2 的题解区发现，时间把分块和二分套树状数组爆了，空间把持久化线段树爆了，在线又把莫队和整体二分爆了，常见算法基本用不上，根据小 Z 的追忆和题解区唯一的非常见算法，我们应该使用 小波矩阵（wavelet matrix）。

如果你不知道什么是小波矩阵，欢迎阅读我的专栏 浅谈 Wavelet Matrix。总之，小波矩阵恰好完美解决了我们的问题。

于是对 a_i,b_i 分别构建一个小波矩阵，在两个小波矩阵上同时二分求解 \opt{rank},\opt{kmin} 即可。

实现上有个小技巧是，手写的 bitset 和小波矩阵都建议使用 0-index，可以省下很多不必要的 ±1 细节。

提交记录，写得太丑了跑得飞慢，以下是核心代码。

struct bits
{
    int n;
    vector <ULL> bit;
    vector <int> cnt;

    #define ppc __builtin_popcountll
    bits() {}
    bits(int _n) : n(_n), bit(_n), cnt(_n) {}
    void set(int k) {bit[k >> 6] |= 1ull << (k & 63);}
    void bld()
        {for (int i : viota(1, n)) cnt[i] = cnt[i - 1] + ppc(bit[i - 1]);}
    int one(int k)
        {return cnt[k >> 6] + ppc(bit[k >> 6] & ((1ull << (k & 63)) - 1));}
    #undef ppc
};

struct wave
{
    int n;
    array <bits, 32> bil, bir;
    array <int, 32> pol, por;

    #define rsp ranges::stable_partition
    #define cmp [&] (int x) {return ~x >> u & 1;}
    wave(vector <int> &arl, vector <int> &arr)
    {
        n = arl.size();
        bil.fill((n >> 6) + 1), bir.fill((n >> 6) + 1);
        pol.fill(0), por.fill(0);
        for (int u : viota(0, 32) | vreve)
        {
            for (int i : viota(0, n))
            {
                if (arl[i] >> u & 1) bil[u].set(i);
                if (arr[i] >> u & 1) bir[u].set(i);
            }
            bil[u].bld(), bir[u].bld();
            pol[u] = rsp(arl, cmp).begin() - arl.begin();
            por[u] = rsp(arr, cmp).begin() - arr.begin();
        }
    }
    void ask(int L, int R, int &v, int k = 0)
    {
        for (int l = L, r = R; int u : viota(0, 32) | vreve)
        {
            int l1 = bil[u].one(l), r1 = bir[u].one(r);
            if (int c = l - l1 - r + r1; ~v >> u & 1) l -= l1, r -= r1;
            else v ^= 1 << u, k += c, l = pol[u] + l1, r = por[u] + r1;
        }
        for (int l = L, r = R; int u : viota(0, 32) | vreve)
        {
            int l1 = bil[u].one(l), r1 = bir[u].one(r);
            if (int c = l - l1 - r + r1; c >= k) l -= l1, r -= r1;
            else v ^= 1 << u, k -= c, l = pol[u] + l1, r = por[u] + r1;
        }
    }
    #undef rsp
    #undef cmp
};

void mainSolve()
{
    int n, q; read(n, q);
    vector lft(n, array {0, 0}), rgt(lft);
    for (int i : viota(0, n))
    {
        int l, r, v; read(l, r, v);
        lft[i] = {l, v}, rgt[i] = {r + 1, v};
    }

    rsort(lft), rsort(rgt);
    vector pol(n, 0), val(pol), por(pol), var(pol);
    for (int i : viota(0, n))
    {
        tie(pol[i], val[i]) = lft[i];
        tie(por[i], var[i]) = rgt[i];
    }
    wave wav(val, var);

    int res = 0;
    static constexpr int LIM = (1 << 21) - 1;
    while (q --)
    {
        int x, y; read(x, y), x ^= res, y ^= res, ++y;
        wav.ask(ruppb(pol, x) - pol.begin(), ruppb(por, x) - por.begin(), y);
        write(res = y), res &= LIM;
    }
}