bitset 维护高维偏序

· · 算法·理论

简单技巧。实用的小 trick。

一般而言多维偏序（比如大于等于 3 维的偏序）做法是 CDQ 分治。但是当维度比较多（比如 5D 以上）时 CDQ 会极其难写，并且带有很多 log，实际效率很劣。

bitset 能够以 O(\frac{n^2d}{w}) 时间和 O(\frac{n^2}{8}) 空间解决这类问题。

方法非常简单：高维偏序，要求我们统计满足在每一维度上的属性都被当前元素偏序的元素的集合。“在每一维度上都被偏序”就是每个维度上的独立偏序条件的逻辑与，在集合上，对应的就是交集。

这可以用 bitset 维护，于是做完了。

具体的，我们设 ans[i] 是一个 bitset，维护被 i 偏序的元素的集合，第 j 位为 1 代表 j 被 i 偏序。那么，我们枚举每个维度，设 f[i] 是这个维度上被 i 偏序的元素的集合（同样，第 j 位为 1 代表 j 在这一维度上被 i 偏序。），令 ans[i] = ans[i] & f[i] 即可。

例题：【模板】三维偏序/陌上花开。以及 CF1826E Walk the Runway，等等。

放一个后面那道题的代码：

#include <bits/stdc++.h>

using namespace std;
int m, n;
array<int, 5005> p;
array<bitset<5005>, 5005> e;
array<long long, 5005> ans;
array<array<int, 5005>, 505> r;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> m >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> r[i][j];
        }
    }

    for (int i = 1; i <= m; ++i) {
        vector<pair<int, int>> tmp(n + 2);
        for (int j = 1; j <= n; ++j) {
            tmp[j] = {r[i][j], j};
        }

        sort(tmp.begin() + 1, tmp.begin() + n + 1);

        bitset<5005> cur;
        cur.set();
        int banned = 0;
        for (int j = 1; j <= n; ++j) {
            while (banned <= n && tmp[banned].first < tmp[j].first) {
                cur[tmp[banned].second] = false;
                banned++;
            }

            e[tmp[j].second] |= cur;
        }

        if (i == m) {
            for (int id: views::values(tmp)) {
                e[id].flip();

                for (int pre = e[id]._Find_first(); pre <= n; pre = e[id]._Find_next(pre)) {
                    ans[id] = max(ans[id], ans[pre]);
                }
                ans[id] += p[id];
            }
        }
    }

    long long final = 0;
    for (int i = 1; i <= n; ++i) {
        final = max(final, ans[i]);
    }
    cout << final;
    return 0;
}