专栏文章

题解：P4848 崂山白花蛇草水

___staring__
P4848题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min080x0
此快照首次捕获于
2025/12/01 18:26
3 个月前
此快照最后确认于
2025/12/01 18:26
3 个月前
查看原文
小波矩阵。。。
这是一篇小波矩阵（wavelet matrix）的题解，严格时空复杂度应为 O(qlog⁡V(log⁡nlog⁡qω+ω))−O(qlog⁡Vlog⁡nω)O(q\log{V}(\log{n}\log{\frac{q}{\omega}} + \omega)) - O(\frac{q\log{V}\log{n}}{\omega})，简单来说也可以是 O(nlog⁡3n)−O(nlog⁡n)O(n\log^3{n})-O(n\log{n})。
如果你不知道什么是小波矩阵，欢迎阅读我的专栏 浅谈 Wavelet Matrix。
本题是动态在线矩形第 k 小，那么延续静态矩形第 k 小的思路：我们把点 (x,y,v)(x,y,v) 按此关键字顺序排序，在序列上先按 vv 构建外层小波矩阵，每一层再按 yy 构建内层小波矩阵。查询在序列上二分出区间，外层做区间第 k 小状物，内层做区间 rank 状物。
考虑动态，直接套上二进制分组就行。因为小波矩阵的结构是固定的，可以在多个矩阵上同时二分。这样是 3log 的。在二进制分组的底层可能在时空上有冗余，可以底层分块，每有 BB 个插入再加入二进制分组。理论取到 B=32/64B=32/64 较优，但是由于二进制分组合并常数太大，实测取到 B=3072B=3072 较快。
也可以把内外小波矩阵的 0/1 数组用平衡树来维护。但要么空间变成 2log，要么时间常数起飞，而且增加码量。
也可以像第一篇题解那样定期重构，这样是 sqrt(log) 的，具体怎么样没测，应该效率会优很多。
B=64B=64 | B=3072B=3072
CPP
struct wave0
{
    vector <pair <ULL, int>> bit;
    #define ppc __builtin_popcountll
    wave0() {}
    wave0(vector <ULL> arr)
    {
        bit.resize((arr.size() >> 6) + 1);
        for (int i : viota(0, ssize(arr))) bit[i >> 6].first |= arr[i] << (i & 63);
        for (int i : viota(1, ssize(bit))) bit[i].second = bit[i - 1].second + ppc(bit[i - 1].first);
    }
    int ask(int k) {return bit[k >> 6].second + ppc(bit[k >> 6].first & ((1ull << (k & 63)) - 1));}
    #undef ppc
};

struct wave1
{
    array <wave0, 20> wav;
    array <int, 20> pos;
    wave1() {}
    wave1(vector <int> arr)
    {
        for (int i : viota(0, 20) | vreve)
        {
            wav[i] = wave0 (arr | vtran([&] (int x) {return x >> i & 1ull;}) | ranges::to <vector> ());
            pos[i] = arr.size() - ranges::stable_partition(arr, [&] (int x) {return ~x >> i & 1;}).size();
        }
    }
    int ask(int l, int r, int x, int y)
    {
        int res = 0;
        for (int lx = l, rx = r, ly = l, ry = r; int i : viota(0, 20) | vreve)
        {
            if (int ll = wav[i].ask(lx), rr = wav[i].ask(rx); ~x >> i & 1) lx -= ll, rx -= rr;
            else res -= rx - rr - lx + ll, lx = pos[i] + ll, rx = pos[i] + rr;
            if (int ll = wav[i].ask(ly), rr = wav[i].ask(ry); ~y >> i & 1) ly -= ll, ry -= rr;
            else res += ry - rr - ly + ll, ly = pos[i] + ll, ry = pos[i] + rr;
        }
        return res;
    }
};

struct wave2
{
    array <wave1, 30> wav;
    array <wave0, 30> bit;
    array <int, 30> pos;
    wave2() {}
    wave2(vector <array <int, 2>> arr)
    {
        for (int i : viota(0, 30) | vreve)
        {
            bit[i] = wave0 (arr | vtran([&] (auto x) {return x[1] >> i & 1ull;}) | ranges::to <vector> ());
            pos[i] = arr.size() - ranges::stable_partition(arr, [&] (auto x) {return ~x[1] >> i & 1;}).size();
            wav[i] = wave1 (arr | vtran([] (auto x) {return x[0];}) | ranges::to <vector> ());
        }
    }
    int ask(int u, int x, int y, int l, int r, int &l0, int &r0, int &l1, int &r1)
    {
        int ll = bit[u].ask(l), rr = bit[u].ask(r);
        l0 = l - ll, r0 = r - rr, l1 = pos[u] + ll, r1 = pos[u] + rr;
        return wav[u].ask(l1, r1, x, y);
    }
};

void staring::mainSolve()
{
    int n, q;
    read(n, q);

    int tot = 0;
    array <wave2, 11> wav;
    vector <array <int, 3>> all, rst;
    constexpr int B = 64;
    auto merge = [&] (int x, int y, int v)
    {
        rst.push_back({x, y, v});
        if (rst.size() < B) return;
        rsort(rst), ++tot;
        for (auto r : rst) all.push_back(r);
        int u = 0; rst.clear();
        while (~tot >> u & 1)
            ranges::inplace_merge(all | vdrop((tot - (2 << u)) * B), all.end() - (B << u)), ++u;
        wav[u] = wave2 (all | vdrop((tot - (1 << u)) * B) |
            vtran([] (auto x) {return array {x[1], x[2]};}) | ranges::to <vector> ());
    };
    auto query = [&] (int x1, int y1, int x2, int y2, int k)
    {
        vector <array <int, 7>> seg;
        for (int i : viota(0, 11))
        {
            if (~tot >> i & 1) continue;
            int l = rlowb(all | vdrop((tot >> i + 1 << i + 1) * B) | vtake(B << i),
                array {x1, y1, 0}) - all.begin() - (tot >> i + 1 << i + 1) * B;
            int r = ruppb(all | vdrop((tot >> i + 1 << i + 1) * B) | vtake(B << i),
                array {x2, y2, 0}) - all.begin() - (tot >> i + 1 << i + 1) * B;
            seg.push_back({i, l, r, 0, 0, 0, 0});
        }

        int resl = 0, resr = (1 << 30) - 1;
        for (int i : viota(0, 30) | vreve)
        {
            int c = 0, resm = resl + (resr - resl >> 1);
            for (auto &[u, l, r, l0, r0, l1, r1] : seg)
                c += wav[u].ask(i, y1, y2 + 1, l, r, l0, r0, l1, r1);
            for (auto [x, y, v] : rst)
                c += x >= x1 && x <= x2 && y >= y1 && y <= y2 && v > resm && v <= resr;
            if (c >= k)
            {
                resl = resm + 1;
                for (auto &[u, l, r, l0, r0, l1, r1] : seg) l = l1, r = r1;
            }   
            else
            {
                resr = resm, k -= c;
                for (auto &[u, l, r, l0, r0, l1, r1] : seg) l = l0, r = r0;
            }
        }
        return resl;
    };

    int res = 0;
    while (q --)
    {
        int t;
        read(t);
        if (t == 1)
        {
            int x, y, v;
            read(x, y, v);
            x ^= res, y ^= res, v ^= res;
            merge(x, y, v);
        }
        else
        {
            int x1, y1, x2, y2, k;
            read(x1, y1, x2, y2, k);
            x1 ^= res, y1 ^= res, x2 ^= res, y2 ^= res, k ^= res;
            res = query(x1, y1, x2, y2, k);
            !res ? write("NAIVE!ORZzyz.") : write(res);
        }
    }
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...