题解-P3810
xfrvq
2021-06-13 15:17:12
[P3810 【模板】三维偏序（陌上花开）](https://www.luogu.com.cn/problem/P3810)
[更好的阅读体验1](https://www.luogu.com.cn/blog/368107/solution-p3810)
[更好的阅读体验2](https://www.cnblogs.com/zeno6174/p/solution-p3810.html)
### 前置算法
+ 树状数组求逆序对
+ 归并排序求逆序对
解题之前，让我们来看一看弱化版本 $\to$ **二维偏序**
---
#### 题意
给定两个长度为数组 $a_1,a_2,\dots,a_n$，$b_1,b_2,\dots,b_n$ 求对于每一个 $i$，$a_j\le a_i$ 且 $b_j\le b_i$ 的 $j$ 有多少个。
#### 解法1
考虑用结构体把数组存起来，对 $a$ 进行排序，再用一个值域树状数组维护 $b$ 值即可。
还没完。由于可能出现 $a_i=a_j$ 且 $b_i=b_j$ 的情况，所以需要去重。
提到去重，就要在结构体里面多加一个 $x$ 。 $x_i$ 表示与 $a_j=a_i,b_j=b_i$ 的 $j$ 的个数，$x_i$ 初始为 $1$
~~去重毒瘤的要死~~
#### 解法2
还是用结构体存，对 $a$ 进行排序+去重，后面考虑用归并排序来求
回想一下归并排序求逆序对，我们求的是 $a_i$ 作为逆序对 $(j,i)$ 的 $j$ 的总个数。
在这里，$a$ 已经按大小排好了，所以我们只考虑对 $b$ 值求逆序对就行了。
**深刻注意解法2**
---
### 三维偏序
进入正题
**第一步**
和二维偏序一样，先按 $a$ 值排好序，去重
**第二步**
为了简化题目，先考虑简易版本**不存在 $a_i=a_j$ 且 $b_i=b_j$ 且 $c_i=c_j$ 的情况**，标准版本放在第三步。
进入到今天的正题： _CDQ_ 讲解部分。
_CDQ_ 分治，顾名思义，是一种分治。而分治，就需要把 $[l,r]$ 分为 $[l,mid]$ 和 $[mid+1,r]$ 。而对于我们要寻找的一个符合 $a_j\le a_i,b_j\le b_i,c_j\le c_i$ 的点对 $(i,j)$ 必须符合以下三种情况之一：
1. $1\le i,j\le mid\gets$ 这在递归处理左半边时已经处理了
1. $mid\lt i,j\le n\gets$ 这在递归处理右半边时已经处理了
1. $1\le i,j\le n\gets$ **这是我们在递归之后需要处理的点对**
按分治三部曲走，接下来就是合并左右区间并统计答案了了，这里按归并排序求逆序对的思路来。
由于 $a,b$ 值都被我们处理好了，接下来就是毒瘤的 $c$ 值，用树状数组维护。
在合并中，我们分两种情况：
1. 此时的最小值在左，那么我们让树状数组的左边那个数的 $c$ 值位置加一
1. 此时的最小值在右，那么我们让答案加上树状数组从 $1$ 到右边数的 $c$ 值位置的和
如果搞不懂为什么左是加，右是查，建议重新看一看归并排序求逆序对。
**注意**：每一次使用完后树状数组要清空。如果单纯 `memset`，会超时（因为是 $O(n)$ ），清空应该对于每一个被存放在树状数组里的 $c_i$ ，其在树状数组里面的值 $-1$
```cpp
int tmp[maxn]; // 临时存放合并好的值的数组
void CDQ(int l,int r){
if(l == r) return;
int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
CDQ(l,mid),CDQ(mid + 1,r); // 递归处理
while(p <= mid && q <= r){ // 合并子区间
if(a[p].b <= a[q].b) bit.update(a[p].c,1),tmp[++len] = a[p++]; // 选左边，此时更新树状数组
else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++]; // 选右边，此时答案要加上值域树状数组的查询
}
while(p <= mid) bit.update(a[p].c,1),tmp[++len] = a[p++]; // 归并左边剩下部分
while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++]; // 归并右边剩下部分
for(int i = l;i <= mid;++i) bit.update(a[i].c,-1); // 清空
for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i]; // 把临时数组里的值拷贝到原数组
}
```
**第三步**
由于第二步只能处理不存在相同的情况，接下来讲解如果存在 $a_i=a_j,b_i=b_j,c_i=c_j$ 的 $(i,j)$ 该怎么处理。
注意刚才我们树状数组是这样更新的：`bit.update(a[p].c,1)`
这里的 `1` 实际上就是 $a_s=a_p,b_s=b_p,c_s=c_p$ 的 $s$ 的个数，记为 $x$ ，$x_i$ 我们在去重时求出。
因此代码如下：
```cpp
int tmp[maxn];
void CDQ(int l,int r){
if(l == r) return;
int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
CDQ(l,mid),CDQ(mid + 1,r);
while(p <= mid && q <= r){
if(a[p].b <= a[q].b) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
}
while(p <= mid) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
for(int i = l;i <= mid;++i) bit.update(a[i].c,-a[i].x);
for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i];
}
```
**第四步**
这时 _CDQ_ 分治已经完成了，我们现在需要统计答案
按照刚才的代码，`a[i].ans` 表示 $a_j\le a_i,b_j\le b_i,c_j\le c_i$ 但不包括 $a_j=a_i,b_j=b_i,c_j=c_i$ 的 $j$ 的个数，而 `a[i].x` 正好表示了 $a_j=a_i,b_j=b_i,c_j=c_i$ 的 $j$ 的个数。于是 `a[i].ans + a[i].x` 就是去重后第 $i$ 个点的答案。
```cpp
for(int i = 1;i <= cnt;++i) res[a[i].ans + a[i].x - 1] += a[i].x; // 注意是 + a[i].x，因为还有与 i 值相同所有 j，其总个数是 a[i].x
for(int i = 0;i < n;++i) printf("%d\n",res[i]);
```
---
[$\color{#52C41A}\texttt{AC CODE}$](https://www.luogu.com.cn/record/51748575)
```cpp
#include<stdio.h>
#include<algorithm>
const int maxn = 114514;
int n,k;
struct BIT{
int t[maxn << 1];
int lowbit(int i){return i & -i;}
void update(int i,int x){for(;i <= k;i += lowbit(i)) t[i] += x;}
int query(int i){int ans = 0;for(;i;i -= lowbit(i)) ans += t[i];return ans;}
} bit; // 树状数组
struct number{
int a,b,c,ans,x;
bool operator<(const number& y) const{return a != y.a ? a < y.a : b != y.b ? b < y.b : c < y.c;}
} a[maxn],tmp[maxn]; // 数的结构体
int res[maxn];
void CDQ(int l,int r){
if(l == r) return;
int mid = l + r >> 1,p = l,q = mid + 1,len = 0;
CDQ(l,mid),CDQ(mid + 1,r);
while(p <= mid && q <= r){
if(a[p].b <= a[q].b) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
else a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
}
while(p <= mid) bit.update(a[p].c,a[p].x),tmp[++len] = a[p++];
while(q <= r) a[q].ans += bit.query(a[q].c),tmp[++len] = a[q++];
for(int i = l;i <= mid;++i) bit.update(a[i].c,-a[i].x);
for(int i = 1;i <= len;++i) a[l + i - 1] = tmp[i];
}
int main(){
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;++i) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c),a[i].x = 1,a[i].ans = 0;
std::sort(a + 1,a + n + 1); // 排序
int cnt = 1;
for(int i = 2;i <= n;++i)
if(a[i].a == a[cnt].a && a[i].b == a[cnt].b && a[i].c == a[cnt].c) ++a[cnt].x; // 如果遇到与 i 一样的，x 值就要自加一
else a[++cnt] = a[i];
CDQ(1,cnt); // 注意不是 CDQ(1,n)
for(int i = 1;i <= cnt;++i) res[a[i].ans + a[i].x - 1] += a[i].x;
for(int i = 0;i < n;++i) printf("%d\n",res[i]);
return 0;
}
```