题解 P3810 【【模板】三维偏序（陌上花开）】
officeyutong
2018-09-25 20:44:18
这道题卡了很长时间，而且蒟蒻还看不懂其他题解中为数不多的二维CDQ分治，最后终于自己搞出来了..
这道题目可以转换为对于每一个三元组，求三个坐标均小于等于它的三元组的个数。
一个三元组只会对三个坐标都大于等于它的三元组造成影响，所以这是一个三维偏序问题，我们可以考虑用CDQ分治来处理。
首先把给定的数据去重，因为CDQ分治对于三个坐标完全一样的元素统计答案会出现问题。
这个过程可以在给第一维排序的过程中顺便解决。
我们需要两个CDQ分治函数（可以压缩到一个），第一个负责给第二维排序，第二个负责给第三位排序。
在给第二维排序的过程中，我们还需要记录下来每一个三元组是在左边还是右边，以方便第三维统计答案（因为第三维在统计答案时需要保证三维都有序），每次对第二维的排序进行完毕后，直接进行第三维排序，同时还要保证第三维排序进行完后，对第二维排序的数组不造成任何影响。
代码中有部分说明。
```cpp
#include <iostream>
#include <algorithm>
#include <assert.h>
#define debug(x) std::cout << #x << " = " << x << std::endl;
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;
const int_t LARGE = 100000;
struct Query
{
int_t pos[3];
int_t mark;
int_t *result = 0;
int_t count = 0;
int_t &operator[](int_t x)
{
return pos[x];
}
bool operator==(const Query &x)
{
for (int_t i = 0; i < 3; i++)
{
if (pos[i] != x.pos[i])
return false;
}
return true;
}
};
Query querys[LARGE + 1];
int_t n, k;
//第二个CDQ分治，对第三维坐标进行排序并统计答案
void process2(Query *querys, int_t left, int_t right)
{
if (left == right)
return;
static Query temp[LARGE + 1];
int_t mid = (left + right) / 2;
process2(querys, left, mid);
process2(querys, mid + 1, right);
int_t uleft = left;
int_t uright = mid + 1;
int_t curr = 0;
//这个for循环写的可能有点晦涩难懂
//大概就是把普通归并排序合并有序表的三个过程直接结合起来了
for (int_t i = left; i <= right; i++)
{
//uleft uright写成了left right
//这种烂错误调了一晚上
//能从左边序列中拿出一个元素的条件是左边序列的第一个元素较小或者右边序列已经为空
if (((uright > right) || querys[uleft].pos[2] <= querys[uright].pos[2]) && uleft <= mid)
{
temp[i] = querys[uleft];
uleft++;
//之所以要加这个判断，是因为我们对第三维的排序打乱了原来的第二维的状态
//所以我们设置了一个标记记录了原来第二维的有序性
//这个标记就是mark，mark为true表示这个查询原来在左边
if (temp[i].mark != 0)
{
//因为元素去重的原因，所以需要乘上元素个数
curr += (temp[i].mark * temp[i].count);
}
}
else
{
temp[i] = querys[uright];
uright++;
if (temp[i].mark == 0)
{
*temp[i].result += curr;
// cout << "counting " << curr << " to " << temp[i] << endl;
}
}
}
std::copy(temp + left, temp + right + 1, querys + left);
}
void process1(Query *querys, int_t left, int_t right)
{
if (left == right)
return;
static Query temp[LARGE + 1];
int_t mid = (left + right) / 2;
process1(querys, left, mid);
process1(querys, mid + 1, right);
int_t uleft = left;
int_t uright = mid + 1;
for (int_t i = left; i <= right; i++)
{
if (((uright > right) || querys[uleft].pos[1] <= querys[uright].pos[1]) && uleft <= mid)
{
temp[i] = querys[uleft];
//需要做好这个标记，因为对第三维排序后第二维就无序了
temp[i].mark = 1;
uleft++;
}
else
{
temp[i] = querys[uright];
//为了防止误统计答案，第二维在右边的需要把标记设置为0
temp[i].mark = 0;
uright++;
}
}
std::copy(temp + left, temp + right + 1, querys + left);
//递归处理第三维
//注意不要把::querys传进去，因为我们process1的作用是对第二维进行排序，如果再调用process2给第三维排序，而且使用的还是同一个数组，那么我们就打乱了第二维的顺序
process2(temp, left, right);
}
int main()
{
int_t _n;
cin >> n >> k;
//保存一下n
_n = n;
//一个内存池，用来记录查询的答案
static int_t results[LARGE + 1];
for (int_t i = 1; i <= n; i++)
{
cin >> querys[i].pos[0] >> querys[i].pos[1] >> querys[i].pos[2];
}
//排序去重
std::sort(querys + 1, querys + 1 + n, [](const Query &a, const Query &b) -> bool {
if (a.pos[0] == b.pos[0])
{
if (a.pos[1] == b.pos[1])
{
return a.pos[2] < b.pos[2];
}
else
{
return a.pos[1] < b.pos[1];
}
}
else
{
return a.pos[0] < b.pos[0];
}
});
//去重
int_t first = 1;
querys[1].count++;
for (int_t i = 2; i <= n; i++)
{
if (querys[i] == querys[first])
{
querys[first].count++;
}
else
{
first = i;
querys[first].count++;
}
}
n = std::remove_if(querys + 1, querys + 1 + n, [](const Query &x) -> bool { return x.count == 0; }) - querys - 1;
//给去重后的每一个元素分配一个int指针用来保存结果，因为我们是在process2中统计结果的，而process2中无法对::querys数组做出修改
for (int_t i = 1; i <= n; i++)
{
querys[i].result = results + i;
}
process1(querys, 1, n);
//结果数组
static int_t result[LARGE + 1];
for (int_t i = 1; i <= n; i++)
{
//因为我们去过重，所以需要给每一个三元组加上这个三元组的个数-1，因为这些东西也对这个三元组的答案做出了贡献
*querys[i].result += querys[i].count - 1;
result[*querys[i].result] += querys[i].count;
}
for (int_t i = 0; i < _n; i++)
cout << result[i] << endl;
return 0;
}
```
博客链接https://yutong.site/?p=722