Luogu P14032 【MX-X20-T6】「FAOI-R7」超级电话

· · 题解

cnblogs。

再遇百万富翁，结果没意识到询问写的是 \mathcal{O}(q2^n) 的光荣倒闭了。

首先考虑 B = 20 该如何处理这个问题。
因为 n = B，又因为操作是基于二进制，所以可以想到分开每一位去看待。

那就相当于是在 [0, 2^n) 的 01trie 上做这个问题。
能够知道在全局异或的值都为 0（即 x 均为 0）时，[0, y] 能在 trie 上被拆成不超过 n 个满子树。
那如果此时全局异或的值 v 不为 0 呢？能发现也是不超过 n 个满子树，v 的第 i 位只相当于影响了第 i 层是先取左儿子还是右儿子。

于是建立 trie，维护每个节点的子树信息即可，A = 2^n - 1。

似乎后面的表述会有些歧义，这里认为 trie 树更低的层指的是是子树大小越小，该层节点数越多的层。

接下来考虑后面的问题：B = 5 / 6 / 7。
此时能够发现 trie 的层数是硬伤，但是为了满足 B 的条件，且依然要基于二进制处理这个问题，我们考虑对 trie 的层进行分块，得到一个压缩后的 trie 树。

具体来说，考虑从高到低每一块分别有 c_1, c_2, \cdots, c_B(c_i\ge 0, \sum c_i = 20) 层，其中第 1 块只有 1 个节点，对于第 i + 1(1\le i\le B) 块，每个第 i 块的节点有 2^{c_i} 个 i + 1 块的儿子，那第 i + 1 块就有 2^{\sum_{j = 1}^i c_j} 个元素。

这样来说就保证了查询时可以每一块至多查询一片，不过这一片该怎么处理呢？
这相当于是对于每个第 i(1\le i\le B) 块的节点，内部还需要建立起一个 [0, 2^{c_i}) 的 01trie，并且对于任意全局异或值和选取的个数都需要保存其信息。
看起来似乎所需要的信息数特别多，不过考虑实际分析后（从高到低分析左右子树选取情况）发现信息数仅为 1 + 2\sum\limits_{i = 0}^{c_i - 1} 4^i，并且因为单独的叶子信息应当是知道的（就是这个节点的各个儿子信息），所以新增的信息数应当为 f(c_i) = 1 + 2\sum\limits_{i = 0}^{c_i - 1} 4^i - 2^{c_i}。

那么对于 c_{1\sim B}，所需要的总信息数量就为 \sum\limits_{i = 1}^B\left(2^{\sum_{j = 1}^{i - 1} c_j}\times f(c_i)\right)。

于是设计一个 dp，f_{i, j} 表示目前选了 c_{1\sim i}，\sum c_k = j 的最小代价。
复杂度为 \mathcal{O}(n^2B)，在跑出了对应的代价后会发现和题目限制完全一致，那就说明做对了。

如果要看这个的代码放在后面了，输出方案可以得到：

对于实现的部分，应当有很多种方法，我觉得我的写法很逆天，建议不要参考。

对于预处理，我因为不知道怎么表示具体的 (x, y) 对应的信息，所以采取的方案是用 xor-hash 后放到哈希表里处理。

对应的处理顺序就是从低到高做，因为高层的节点需要低层的信息。

在处理块内 trie 的信息时，我是从低到高每次合并相邻的两个子树，具体来说就是维护每个子树的 (v, S)，其中 v 是整个子树的信息，S 是整个子树在得到 (x, y) 后可能划分出的信息（不包括整个子树的 v）。
那么可以知道 (v, S), (u, T) 合并后得到的就是 (v\oplus u, S\cup T \cup (\bigcup_{x\in S} x\oplus u) \cup (\bigcup_{x\in T} v\oplus x)\cup \{u, v\})。
重复这个操作 c_i 次即可。

对于询问，如果暴力就是 \mathcal{O}(2^n) 复杂度不可接受。
又因为我的做法不能很好的定位，我的做法是首先从高到低定位出每一块，然后在第 i 块中暴力分解这一块所需的信息，这样复杂度就降到了\mathcal{O}\left(\sum\limits_{i = 1}^n 2^{c_i}\right)。
这里的暴力分解指的是，直接求出 \{ x\oplus i \mid i\in [0, y)\} 的 xor-hash 值再查表。

两部分的复杂度都不能很好表示出来，能过就对了。

输出方案（这里输出的是压缩 trie 树从低到高的 c_i）：

    for (int i = 1; i <= 10; i++) {
        val[i] = 1;
        for (int j = 1, x = 2; j <= i; j++) {
            val[i] += x, x *= 4;
        }
        val[i] -= (1 << i);
    }
    memset(dp, 0x3f, sizeof(dp)), dp[0][0] = 0;
    for (int i = 0; i <= 20; i++) {
        for (int j = 1; i + j <= 20 && j <= 10; j++) {
            for (int k = 0; k < 7; k++) {
                if (chkmin(dp[i + j][k + 1], dp[i][k] + (1ll << i) * val[j])) {
                    lst[i + j][k + 1] = j;
                }
            }
        }
    }

    for (int step : {5, 6, 7}) {
        for (int i = 20, j = step; j; j--) {
            printf("%d ", lst[i][j]);
            i -= lst[i][j];
        }
        puts("");
    }

通过代码：

#include <bits/extc++.h>

using ull = unsigned long long;

constexpr int maxm = 1e7 + 10;
const std::vector<int> way[8] = {
    {},
    {},
    {},
    {},
    {},
    {1, 2, 3, 5, 9},
    {1, 1, 2, 3, 5, 8},
    {1, 1, 1, 2, 3, 4, 8}
};

int B;

int tot = 1 << 20, totr = 1 << 20;
std::mt19937_64 rand_(std::chrono::steady_clock::now().time_since_epoch().count());
ull rnd[maxm];
__gnu_pbds::cc_hash_table<ull, int> id;
std::vector<int> son[maxm];

void assign(int x, int y, int z);

void init(int n_, int m_, int A_, int B_) {
    B = std::min(B_, 7);

    for (int i = 0; i < (1 << 20); i++) {
        rnd[i] = rand_();
    }

    auto add = [&](ull x, ull y) {
        id[x ^ y] = tot;
        assign(id[x], id[y], tot);
        tot++;
    };

    std::vector<std::pair<ull, int>> arr;
    for (int i = 0; i < (1 << 20); i++) {
        arr.emplace_back(rnd[i], i), id[rnd[i]] = i;
    }
    for (int d : way[B]) {
        std::vector<std::pair<ull, int>> newa;
        for (int l = 0; l < arr.size(); l += 1 << d) {
            std::vector<std::pair<ull, std::vector<ull>>> group;
            for (int i = 0; i < (1 << d); i++) {
                son[totr].push_back(arr[l + i].second);
                group.push_back({arr[l + i].first, {}});
            }
            for (int j = 0; j < d; j++) {
                std::vector<std::pair<ull, std::vector<ull>>> newg;
                for (int i = 0; i < group.size(); i += 2) {
                    const auto x = group[i];
                    const auto y = group[i + 1];
                    std::vector<ull> part{x.first, y.first};
                    for (auto val : x.second) {
                        part.push_back(val);
                        add(val, y.first);
                        part.push_back(val ^ y.first);
                    }
                    for (auto val : y.second) {
                        part.push_back(val);
                        add(x.first, val);
                        part.push_back(x.first ^ val);
                    }
                    add(x.first, y.first);
                    newg.push_back({x.first ^ y.first, part});
                }
                group = newg;
            }
            newa.emplace_back(rnd[totr] = group.front().first, totr);
            totr++;
        }
        arr = newa;
    }
}

int all = 0;
inline int conv(int x) {
    return x < (1 << 20) ? (x ^ all) : x;
}
std::vector<int> query(int x, int y) {
    all ^= x, y++;

    if (y == (1 << 20)) {
        return {tot - 1};
    }

    std::vector<int> ans;
    int sum = 20;
    for (int d = B - 1, u = totr - 1; d >= 0; d--) {
        int s = way[B][d];
        sum -= s;
        int xv = (all >> sum) & ((1 << s) - 1);
        int yv = (y >> sum) & ((1 << s) - 1);
        if (yv) {
            ull val = 0;
            for (int i = 0; i < yv; i++) {
                val ^= rnd[son[u][i ^ xv]];
            }
            ans.push_back(conv(id[val]));
        }
        u = son[u][xv ^ yv];
    }
    return ans;
}