rt

bitset乱搞多维偏序

思路

as we all know ， $k$ 维偏序可以叠 CDQ 在 $O(n \log^{k - 1} n)$ 的时间内解决，但当 $k$ 很大的时候，还不如暴力，所以，我们用 bitset + 暴力解决多维偏序，不失为一种方法

思路很暴力，值域分块，记 $rk[i][j]$ 表示“第 $i$ 维值为 $j$ 的数说第几个”，再开一个 bitset<N> ct[K][NB] 记 $ct[i][j]$ 表示“第 $i$ 维值在第 $j$ 块中的数”，对 $ct[i][]$ 做一个前缀或方便查询，然后直接枚举每个数，暴力查每一维比它小的数的集合，取交即可

时间 $O(\frac{n^2k}{w})$ ，空间 $O(\frac{n^{1.5}k}{w})$

代码

#include <bits/stdc++.h>
using LL = long long;
const int K = 10 + 5, N = 1e5 + 100, B = 320, NB = 320;
int k, n, num = 0, a[N][K], l[N], r[N], rk[K][N], id[N];
std::bitset<N> ct[K][NB], tp, as, now;
LL ans = 0;
bool work(int w, int x) //w:维度x:值
{
    tp = ct[w][id[x] - 1];
    for (int i = l[id[x]]; i < x; ++i) tp.set(rk[w][i]);
    as &= tp;
    return as.any();
}
int main()
{
    scanf("%d %d", &k, &n);
    for (int j = 1; j <= k; ++j)
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i][j]), rk[j][a[i][j]] = i;
    for (int i = 1; i <= n; i += B) l[++num] = i, r[num] = i + B - 1;
    r[num] = n;
    for (int i = 1; i <= n; ++i) id[i] = (i - 1) / B + 1; 
    for (int i = 1; i <= k; ++i) ct[i][0].reset();
    for (int i = 1; i <= k; ++i)
        for (int j = 1, o; j <= num; ++j)
            for (ct[i][j] = ct[i][j - 1], o = l[j]; o <= r[j]; ++o) ct[i][j].set(rk[i][o]);
    for (int i = 1, j; i <= n; ans += as.count(), ++i)
        for (now.set(i), as = now, j = 1; j <= k && work(j, a[i][j]); ++j);
    printf("%lld\n", ans);
    return 0;
}