OI集训 Day3

Content： Data structs
Date：2025.7.19

内容

• 三维偏序问题
• CDQ分治
• 整体二分
• 分块
• 莫队算法

具体内容

三维偏序问题

问题描述

给定一些三元组 $(a_i, b_i, c_i)$，询问对于三元组 $(a_j, b_j, c_j)$，有多少个三元组满足 $a_i \le a_j$ 且 $b_i \le b_j$ 且 $c_i \le c_j$。

首先对于这个问题，我们考虑先去重，然后排序。排序规则如下：

• 如果 $a_i \ne a_j$，则返回 $a_i < a_j$
• 如果 $b_i \ne b_j$，则返回 $b_i < b_j$
• 否则返回 $c_i < c_j$

这样我们就把 $a_i < a_j$ 的条件去掉了。

接下来我们考虑分治，定义函数 $solve(l, r)$ 表示当前解决到了区间 $[l, r]$，取其中点 $mid$，将原序列的问题转化为三个部分：

• $j < i \le mid$，由 $solve(l, mid)$ 解决。
• $mid < j < i$，由 $solve(mid + 1, r)$ 解决。
• $j \le mid < i$，即被 $mid$ 分成了两个部分。

对于第三种情况，我们需要解决的是如下问题：

问题描述

在区间 $[l,r]$ 中，有多少对二元组 $(i, j)$ （其中 $i \ne j$）满足 $b_i < b_j$ 且 $c_i < c_j$。

可见问题转化为了二维偏序问题，用线段树解决就可以。

整体二分

普通的二分操作是直接对于每个询问二分答案，判断答案是否合法。
整体二分的思路是将所有询问一起二分，根据二分的答案对询问进行分类，再逐步求解。

例题：