Shannon’s Channel

P3810 【模板】三维偏序 / 陌上花开#

题目链接： P3810 三维偏序

这是最经典的三维偏序问题。给定 $n$ 个三元组 $(a_i,b_i,c_i)$，对于每个点，统计三个维度都不超过它的点的数量，最后再统计每种数量分别对应多少个点。

这道题的整体思路正如前面所说：先排序处理第一维，再用 CDQ 分治处理第二维，最后用树状数组维护第三维的前缀和。排序后，第一维的条件已经由点的顺序保证；在 CDQ 的合并过程中，左右区间分别按照第二维扫描；当左侧点满足第二维条件时，将它加入树状数组，查询右侧点的第三维前缀和，就得到了三维条件同时满足时的贡献。

实现时首先需要处理完全相同的点。相同的三元组在统计时也要互相贡献，如果直接把它们当成独立点处理，会产生重复计算。因此先按照 $(a,b,c)$ 排序，将连续出现的相同点合并，记录这一组点的数量 cnt。之后只对合并后的点进行 CDQ 分治，最后再把这一组点的贡献还原给原来的 cnt 个点。

CDQ 的递归部分只计算跨越左右区间的贡献。递归处理完左右区间后，枚举右区间的点，并用双指针扫描左区间。对于当前右侧点 $j$，只要左侧点 $i$ 满足 $b_i\le b_j$，就把它的 $c_i$ 加入树状数组；随后查询 query(c_j)，即可得到左区间中同时满足第二维和第三维条件的点数。加入树状数组的增量不是 $1$，而是该点的 cnt，因为一个合并点代表了多个完全相同的原始点。

扫描结束后，要把本轮加入树状数组的左侧点全部撤销，避免它们影响其他递归区间。最后再将整个 $[l,r]$ 区间按照第二维排序，使当前区间在返回上一层时保持整体有序。这里可以直接使用 sort 简化代码；如果改成归并排序，就可以在合并两个已有序区间的同时完成排序。

需要注意比较符号和题目的定义保持一致。这里树状数组加入条件使用 $b_i\le b_j$，查询使用 $c_i\le c_j$，对应题目中“每一维不超过”的偏序关系。如果题目要求严格小于，就需要同步修改排序、双指针和树状数组查询的边界。

相同点合并后，设某个点的 CDQ 贡献为 ans，那么它对应的统计数量为 ans + cnt - 1：ans 来自其他点，cnt - 1 来自同组中除自身以外的重复点。最后将这个数量对应的答案计数增加 cnt，即可恢复所有原始点的结果。

复杂度： 初始排序和相同点合并需要 $O(n\log n)$。CDQ 分治有 $O(\log n)$ 层，每层树状数组的修改和查询为 $O(\log n)$，因此总时间复杂度为 $O(n\log^2 n)$，额外空间复杂度为 $O(n)$。

Grand Swap Master#

题目链接： Grand Swap Master

这道题的关键不在于直接模拟操作，而是先对题目中的式子进行数学化简。化简之后，可以把一个位置表示成二维点 $(A_i,B_i)$，原问题转化为统计满足特定偏序关系的点对：一维满足严格大小关系，另一维满足对应的大小关系。除此之外，$i$ 和 $j$ 相邻，以及 $i$ 或 $j$ 位于 $1$、$n$ 等边界位置时，原来的推导不再适用，需要单独讨论。

因此，算法分成两部分。首先把相邻位置和边界位置产生的贡献直接用公式计算出来，记入 base；然后只处理满足一般情况的点对。这样可以避免在 CDQ 中混入边界条件，让分治部分只负责统一的二维偏序统计。

对于一般情况，令

将所有点按照 $x$ 从小到大排序，之后第一维的关系就由数组顺序保证。接下来只需要使用 CDQ 分治处理第二维 $y$。每次递归仍然只统计跨越左右区间的贡献：右区间的点依次扫描，左区间的点通过双指针加入统计范围，再根据 $y$ 的关系累加答案。

代码中排序时对 $x$ 相同的点按照 $y$ 从大到小排列。这个 tie-break 是为了配合题目要求的严格关系：当第一维相同时，利用第二维的反向顺序，避免相等的第一维被错误地当成合法的先后关系。进入 CDQ 合并后，区间会按照 $y$ 排序；双指针通过跳过不满足条件的左侧点，直接统计当前右侧点对应的左侧数量。

这部分代码不需要树状数组，因为当前只需要知道满足第二维条件的左侧点个数，不需要再对第三维进行前缀查询。双指针移动到位置 i 时，i - l 就是已经满足条件的左侧点数量，将它累加到 add 即可。

这里的判断只写成 p[i].y < p[j].y，并不是只统计两维都变小的情况。数学化简后，合法点对满足

也就是两维同时变小，或者两维同时变大。由于统计的是点对而不是有向关系，后一种情况交换 $i,j$ 的顺序后，就变成了前一种情况。将点按照 $x$ 从小到大排序后，每个合法点对都会唯一地表现为左侧点的 $x$、$y$ 都小于右侧点，因此 CDQ 只需要统计 x_left < x_right 且 y_left < y_right。两维都大于的情况已经以相反的下标顺序被包含在其中了。

最后还要处理相邻位置的重复统计。相邻点对在一般二维偏序中可能已经被 CDQ 统计过，但它们在原题中属于前面单独讨论的特殊情况，所以用 adj 记录这些被重复计算的数量，最终答案为：

其中 base 是边界和特殊位置直接计算出的贡献，add 是 CDQ 对一般点对统计出的贡献，adj 则是需要从中扣除的相邻点对。

复杂度： 特殊情况的处理是线性的。对一般点按照 $x$ 排序后，CDQ 分治每层进行线性双指针扫描，若每层使用 sort 重新按照 $y$ 排序，则总时间复杂度为 $O(n\log^2 n)$，额外空间复杂度为 $O(n)$。如果将最后的排序改为归并，可以把排序部分优化为 $O(n\log n)$。

病毒片段#

题目链接： 病毒片段

这道题在赛后补题时，常见的做法是扫描线加线段树。这里换一种更直接的方式，只使用 CDQ 分治完成同样的二维偏序查询。

一个病毒片段可以表示为区间 $[l_i,r_i]$，它的长度是

对于询问区间 $[L,R]$，需要在满足

的所有病毒片段中取最大长度。原始条件的一维是“向右”，不符合标准的左下偏序，因此将左端点取反：

询问点同样取为

于是条件变成

这就是标准的二维偏序。点的权值也可以写成

因此只需要查询左下矩形中的最大点权。

把病毒片段作为 type = 0 的点，把询问作为 type = 1 的点，所有点按照第一维 $x$ 排序后放入同一个数组。CDQ 递归处理左右区间，合并时只让左侧的病毒点对右侧的询问产生贡献：左右区间按第二维 $y$ 扫描，当左侧点满足 $y_i\le y_j$ 时，将它的权值加入当前最大值；右侧询问直接用这个最大值更新答案。

第一维相等时，排序让病毒点排在询问之前，这样 $x_i=X$ 的边界点可以被查询包含。第二维同样使用 <=，对应题目中的 $r_i\le R$。

CDQ 的每一层处理完贡献后，还要将整个区间按照 $y$ 排序，保证返回上一层时左右区间已经具备归并扫描所需的顺序。代码使用 sort 可以简化实现；如果改为归并排序，则可以在线性时间内完成这一层的整体排序。

当某个询问没有匹配的病毒片段时，维护的答案仍是负无穷，输出时再与 $0$ 取最大值即可。这样既能正确表示“没有可选区间”，也不会因为把初值设成 $0$ 而掩盖点权可能为负的情况。

复杂度： 将所有病毒片段和询问一起排序后，使用 sort 完成每层按 $y$ 的重排，时间复杂度为 $O((n+q)\log^2(n+q))$，额外空间复杂度为 $O(n+q)$。若使用归并维护 $y$ 的有序性，排序部分可以优化到 $O((n+q)\log(n+q))$。