三位偏序(bitset)

更新于 2026年9月26日约 4 分钟阅读

upd on 2025/9/9:改正一处笔误,感谢 @nlxxjy。

题目链接:P3810 【模板】三维偏序(陌上花开)

可能更坏的阅读体验

蒟蒻不会 CDQ 分治,不会 KD-Tree,不会树套树,只能用最简单的 bitset 做了。

题目分析

多维偏序,就是求哪个元素所有的属性都比另一个元素小。三维偏序,就是属性个数为 33 的情况。

O(n2)O(n^2) 暴力肯定是不行的,紫色的难度和 10510^5 的数据范围都不允许这么做。

考虑用 bitset 表示一个维度属性值小于等于一个元素的所有元素的集合,由于题目要求三个维度都要满足,所以对三个维度的集合求交集,最后交集的元素个数减一(排除自身),就求出了题目中的 f(i)f(i)。

下面是 bitset 相关的操作:

  • 初始化:set() 初始化全为 11,reset() 初始化全为 00。
  • 求交集(A∩BA\cap B):A&B 也就是按位与。
  • 求元素个数:count() 可以计算出所有为 11 的位的个数。

为什么用 bitset?

bitset 相关的操作由于是计算机按位进行的,在 64-bit 的计算机运行自带一个 164\frac{1}{64} 的常数,可以高效解决集合运算等操作。

算法介绍

对 aa、bb、cc 分别排序,并求出排序后的数在原数组对应的下标。

由于空间限制,把所有元素分成每 10410^4 个元素为一组的小组来处理。

设 10410^4 个 bitset BiB_i,和一个辅助 bitset SS。

BiB_i 表示所有小于等于小组中第 ii 个元素的元素构成的集合,初始全为 11(后面要按位与)。

对于每个维度分别处理:

  • 清空 SS(初始化全为 00)。
  • 使用指针 ptrptr 动态构建 SS:
    • SS 存储所有当前维度属性值 ≤\le 当前元素 curcur 的元素。
    • 指针 prtprt 从 1 开始,当 ptrptr 指向的属性值 ≤cur\le cur 的属性值时,设置对应位为 11(ptrptr 同时自增)。
  • 如果当前元素 curcur 在组内,则取交集,保留同时满足当前维度的元素。

处理完三个维度后,统计结果(记得减去自身)。

正确性证明

正确性是显然的。

时间复杂度

排序:O(nlog⁡n)O(n \log n)。

分组处理:组数 O(n/M)≈O(10)O(n/M) \approx O(10)(MM 是组的大小 =104=10^4)。

每组内:每个维度 O(n)O(n) 构建 SS,O(M⋅n/w)O(M \cdot n / w) bitset 交集操作(ww 为机器字长,通常是 6464)。

总时间:O(3⋅nlog⁡n+3⋅(n/M)⋅(n+M⋅n/w))≈4.8×108O(3\cdot n \log n +3 \cdot (n/M) \cdot (n + M \cdot n / w)) \approx 4.8 \times 10^8,可以非常极限地通过本题。

空间复杂度

bitset bib_i:104×10510^4\times 10^5 bit ≈120\approx 120 Mib。

其他数组:O(n)O(n)。

代码实现

看算法介绍太抽象了,还是看代码吧。

详细注释

#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=10000; //N:最大元素数量,M:每组处理的最大元素数量
int n,k; //n:元素数量,k:最大属性值(没用)
int a[3][N]; //a[i][j]:第j个元素的第i维属性值(i=0,1,2对应a,b,c)
int p[3][N]; //p[i][j]:按第i维属性值排序后,第j小的元素的原始编号(索引)
int ans[N]; //ans[i]:统计f(x)=i的元素个数
bitset<N>b[M+1]; //b[i]:第i个元素对应的bitset,记录哪些元素在所有维度都比i小
bitset<N>s; //s:临时辅助bitset,用于处理当前维度的偏序
int main(){
    cin.tie(0)->sync_with_stdio(0); //优化输入输出速度
    cin>>n>>k; //k是没用的
    for(int i=1;i<=n;i++)
        cin>>a[0][i]>>a[1][i]>>a[2][i], //读入第i个元素的三维属性
        p[0][i]=p[1][i]=p[2][i]=i; //初始化索引数组
    for(int i=0;i<3;i++) //对三个维度分别排序
        sort(p[i]+1,p[i]+1+n,[i](int x,int y){ //lambda表达式,[i]表示捕获变量i的值
            return a[i][x]<a[i][y]; //按照第i维的属性值升序排序
        });
    for(int l=1,r;l<=n;l=r+1){ //分组处理,每组最多M个元素
        r=min(n,l+M-1); //确定当前组的右边界
        for(int i=1;i<=M;i++)
            b[i].set(); //set()将bitset所有位置初始化为1
        for(int i=0;i<3;i++){ //对三个维度依次处理
            s.reset(); //清空临时bitset
            int ptr=1; //指针指向当前已处理到的元素位置
            for(int j=1;j<=n;j++){ //按第i维的排序顺序处理每个元素
                int cur=p[i][j]; //当前处理的元素编号
                while(ptr<=n&&a[i][p[i][ptr]]<=a[i][cur])
                    s[p[i][ptr++]]=1; //将所有在第i维上不大于cur的元素在s中标记为1
                if(l<=cur&&cur<=r) //如果当前元素在本组处理范围内
                    b[cur-l+1]&=s; //按位与操作求两个集合的交集
            }
        }
        for(int i=l;i<=r;i++) //统计当前组每个元素的答案
            ans[b[i-l+1].count()-1]++; //count()返回bitset中1的个数
        //减1是因为要排除自己(j!=i)
    }
    for(int i=0;i<n;i++) //输出结果
        cout<<ans[i]<<'\n'; //ans[i]表示f(x)=i的元素个数
    return 0;
}

无注释

#include <bits/stdc++.h>
using namespace std;
const int N=100010,M=10000;
int n,k,a[3][N],p[3][N],ans[N];
bitset<N>b[M+1],s;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[0][i]>>a[1][i]>>a[2][i],
        p[0][i]=p[1][i]=p[2][i]=i;
    for(int i=0;i<3;i++)
        sort(p[i]+1,p[i]+1+n,[i](int x,int y){
            return a[i][x]<a[i][y];
        });
    for(int l=1,r;l<=n;l=r+1){
        r=min(n,l+M-1);
        for(int i=1;i<=M;i++)
            b[i].set();
        for(int i=0;i<3;i++){
            s.reset();
            int ptr=1;
            for(int j=1;j<=n;j++){
                int cur=p[i][j];
                while(ptr<=n&&a[i][p[i][ptr]]<=a[i][cur])
                    s[p[i][ptr++]]=1;
                if(l<=cur&&cur<=r)
                    b[cur-l+1]&=s;
            }
        }
        for(int i=l;i<=r;i++)
            ans[b[i-l+1].count()-1]++;
    }
    for(int i=0;i<n;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

AC 记录(最慢的点 900900 ms)。

拓展阅读

关于高维偏序,给大家推荐一个课件。

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC