HihoCoder - 1513 bitset 处理五维偏序

题意：给出 $n < 3 e 4$ 个有序组 $(a, b, c, d, e)$ ，求对第 $i$ 个有序组有多少个 $j$ 满足 $(a_{j} < a_{i}, b_{j} < b_{i}, c_{j} < c_{i}, d_{j} < d_{i}, e_{j} < e_{i})$

五维偏序问题按套路来可以排序 + 树套树套树套树 (打死

然而这是显然连 $O (n^{2})$ 暴力都不如的

可是题目给 4s， $O (n^{2})$ 是不可能的，但在神奇的 bitset 加持下 $O (5 * n^{2} / 32)$ 的时空复杂度是可以卡过去的！

用 bitset 表示集合， $b i t [i] :$ 如果 $i$ 在集合中就设为 1，否则 0

维护 $b i t [i] [j]$ ，表示排在第 $j$ 个关键字的第 $i$ 名前面的集合状态

如果 $r a n k [k] < r a n k [i]$ ，则置 $b i t [i] [j] [k] = 1$

这里如果是有序的就可以直接利用 bitset 的 $O (n^{2} / 32)$ 构造进行暴力传递

然后对 5 个关键字的集合求交就可以得出各个答案

#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iter(i,j) for(int i=0;i<(j).size();i++)
#define print(a) printf("%lld",(ll)a)
#define println(a) printf("%lld\n",(ll)a)
#define printbk(a) printf("%lld ",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int MAXN = 3e4+11;
const int oo = 0x3f3f3f3f;
typedef long long ll;
ll read(){
    ll x=0,f=1;register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int a[MAXN][6],ra[MAXN][6];
bitset<MAXN> bs[MAXN][6],t;
int main(){
    int n;
    while(cin>>n){
        rep(i,0,n) rep(j,1,5) bs[i][j].reset();
        rep(i,1,n) rep(j,1,5) ra[a[i][j]=read()][j]=i;
        rep(i,2,n) rep(j,1,5){
            bs[i][j]=bs[i-1][j];
            bs[i][j][ra[i-1][j]]=1;
        }
        rep(i,1,n){
            t=bs[a[i][1]][1];
            rep(j,2,5) t&=bs[a[i][j]][j];
            println(t.count());
        }
    }
    return 0;
}