三维偏序（bitset 做法）

模板题目链接 洛谷文章链接

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

题目分析

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

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

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

下面是 bitset 相关的操作：

• 初始化：set() 初始化全为 $1$，reset() 初始化全为 $0$。
• 求交集（$A\cap B$）：A&B 也就是按位与。
• 求元素个数：count() 可以计算出所有为 $1$ 的位的个数。

为什么用 bitset？

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

算法介绍

对 $a$、$b$、$c$ 分别排序，并求出排序后的数在原数组对应的下标。

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

设 $10^4$ 个 bitset $B_i$，和一个辅助 bitset $S$。

$B_i$ 表示所有小于等于小组中第 $i$ 个元素的元素构成的集合，初始全为 $1$（后面要按位与）。

对于每个维度分别处理：

• 清空 $S$（初始化全为 $0$）。
• 使用指针 $ptr$ 动态构建 $S$：
  • $S$ 存储所有当前维度属性值 $\le$ 当前元素 $cur$ 的元素。
  • 指针 $prt$ 从 1 开始，当 $ptr$ 指向的属性值 $\le cur$ 的属性值时，设置对应位为 $1$（$ptr$ 同时自增）。
• 如果当前元素 $cur$ 在组内，则取交集，保留同时满足当前维度的元素。

处理完三个维度后，统计结果（记得减去自身）。

正确性证明

正确性是显然的。

时间复杂度

排序：$O(n \log n)$。

分组处理：组数 $O(n/M) \approx O(10)$（$M$ 是组的大小 $=10^4$）。

每组内：每个维度 $O(n)$ 构建 $S$，$O(M \cdot n / w)$ bitset 交集操作（$w$ 为机器字长，通常是 $64$）。

总时间：$O(3\cdot n \log n +3 \cdot (n/M) \cdot (n + M \cdot n / w)) \approx 4.8 \times 10^8$，可以非常极限地通过本题。

空间复杂度

bitset $b_i$：$10^4\times 10^5$ bit $\approx 120$ Mib。

其他数组：$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表达式
			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的元素标记为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 记录（最慢的点 $900$ ms）。

拓展阅读

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