题解：P3810 【模板】三维偏序（陌上花开）
csxx601cjy
·
·
题解
upd on 2025/9/9：改正一处笔误，感谢 @nlxxjy。
题目链接：P3810 【模板】三维偏序（陌上花开）
可能更好的阅读体验
蒟蒻不会 CDQ 分治，不会 KD-Tree，不会树套树，只能用最简单的 bitset 做了。
题目分析
多维偏序，就是求哪个元素所有的属性都比另一个元素小。三维偏序，就是属性个数为 3 的情况。
考虑用 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)$。
### 代码实现
看算法介绍太抽象了，还是看代码吧。
#### 详细注释
```cpp
#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;
}
```
#### 无注释
```cpp
#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 记录](https://www.luogu.com.cn/record/224316592)（最慢的点 $900$ ms）。
### 拓展阅读
关于高维偏序，给大家推荐一个[课件](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/zdo2hke0)。