P3810 【模板】三维偏序（陌上花开）（bitset）
panyf
·
·
题解
提供一篇 bitset 的题解。
bitset 可以用来求解高维偏序问题，记 m 为维数，则时间复杂度为 O(\dfrac{n^2m}{w})。
开 n 个 bitset，b_{i,j}=1 表示 j 每一维都不超过 i。初始化所有 b_{i,j}=1。
先枚举每一维，然后对所有数按这一维排序。
开一个新的 bitset s，按这一维从小到大处理所有数，处理到 i 时 s_j=1 表示当前维 j 不超过 i。
每次 `b[i]&=s` 即可。
$100000$ 的 bitset 开不下，要用分组 bitset。
就是将点分为若干组，每组 $B$ 个，每次只求出这 $B$ 个点对应的 bitset，这样只需要开 $B$ 个 bitset。
可能略微卡常。
[AC 提交记录](https://www.luogu.com.cn/record/51314650)
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
int p[3][N],a[3][N],w[N];
bitset<N>b[9999],s;
int main(){
int*tp,*ta,n,l,r,i,j,k,o;
for(i=1,scanf("%d%*d",&n);i<=n;++i)for(j=0;j<3;++j)scanf("%d",a[j]+i),p[j][i]=i;
for(i=0;i<3;++i)sort(p[i]+1,p[i]+n+1,[=](int x,int y){return a[i][x]<a[i][y];});//按每一维排序
for(l=1;l<=n;l=r+1){//分组bitset，每组9991个
for(i=l,r=min(l+9991,n);i<=r;++i)b[i-l].set();
for(i=0;i<3;++i)for(tp=p[i],ta=a[i],s.reset(),j=k=1;j<=n;++j){
for(o=tp[j];k<=n&&ta[tp[k]]<=ta[o];)s[tp[k++]]=1;
if(l<=o&&o<=r)b[o-l]&=s;
}
for(i=l;i<=r;++i)++w[b[i-l].count()];
}
for(i=1;i<=n;++i)printf("%d\n",w[i]);
return 0;
}
```