某多序列二分的神秘做法

Pentiment · 2025-03-05 16:22:44 · 算法·理论

给你 k 个序列，每个序列的长度都为 n，q 次询问，对于每个序列求出 x 的排名/前驱/后继等。

显然有一个单次询问 \mathcal O(k\log n) 的暴力。

有一个东西叫分散层叠，但我显然是不会这玩意的，但今上午上 whk 的时候乱想了一个做法，时间常数比分散层叠优秀得多，缺点在于空间是 \mathcal O(nk\log n) 的，有可能会被毒瘤出题人卡空间。

以后继为例，首先有另外一种暴力：把所有的序列都揉到一起排序，对于每个位置 i 预处理 \text{suf}_{i,j} 表示 i 位置上的数在序列 j 上的后缀，这个可以从大往小扫维护一个 \text{buc}，预处理复杂度为 \mathcal O(nk^2)，查询复杂度为 \mathcal O(\log n+k)。

考虑平衡这两个暴力，每 \log n 个序列揉到一起排序，像上面那样做即可，预处理复杂度降到了 \mathcal O(nk\log n)，单次查询复杂度仍是 \mathcal O(k) 的。

模板题代码：

const int N = 10005;
int n, k, Q, d, tot[9], blen[9], suf[9][N * 12][12];
pair<int, int> a[9][N * 12];
int main() {
    cin >> n >> k >> Q >> d;
    for (int i = 0, x, b; i < k; i++) {
        blen[b = i / 12]++;
        for (int j = 1; j <= n; j++) cin >> x, a[b][++tot[b]] = {x, i % 12};
    }
    int btot = (k - 1) / 12;
    for (int i = 0; i <= btot; i++) {
        sort(a[i] + 1, a[i] + 1 + tot[i]);
        int buc[12]; memset(buc, 0, sizeof(buc));
        for (int j = tot[i]; j >= 1; j--) {
            buc[a[i][j].second] = a[i][j].first;
            for (int k = 0; k < 12; k++) suf[i][j][k] = buc[k];
        }
    }
    int ans = 0, x;
    for (int q = 1; q <= Q; q++) {
        cin >> x, x ^= ans, ans = 0;
        for (int i = 0, p; i <= btot; i++) {
            p = lower_bound(a[i] + 1, a[i] + 1 + tot[i], make_pair(x, 0)) - a[i];
            for (int j = 0; j < blen[i]; j++) ans ^= suf[i][p][j];
        }
        if (!(q % d)) cout << ans << '\n';
    }
}

跑得很快，仅次于针对题目乱搞的做法。