主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
P3810 【模板】三维偏序（陌上花开）
最后更新于 2025-08-28 09:13:03
作者
2huk
分类
题解
题解
P3810
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
考虑二维偏序。 我们将所有点按某一维排序，然后按照这一位扫描线。这样操作的目的是把这一维变成时间维。 然后维护一个树状数组，在扫描的过程中做在线的一维偏序。这是简单的。 这给了我们一个启示：离线的 $x$ 维偏序与在线的 $x - 1$ 维偏序的难度相同。做法就是将某一维转化成时间维。 同理对于三维偏序我们要做在线的二维偏序。考虑 cdq 分治。 首先按 $x$ 排序。 定义函数 $\text{solve}(l, r)$ 表示求有多少对 $(i, j)$ 满足 $l \le i \le j \le r$ 且满足三维偏序的要求。那么我们执行三个步骤： - $\text{solve}(l,mid)$； - $\text{solve}(mid+1,r)$； - 计算有多少 $(i, j)$ 满足 $l \le i \le mid$ 且 $mid < j \le r$。 对于第三个，显然左边的 $x$ 一定小于右边的 $x$。所以这一维无需考虑。 我们再将左右两边分别按 $y$ 排序，然后双指针扫描。这样就满足 $y$ 的条件。 再套一个树状数组就能满足 $z$ 的条件。
正在渲染内容...
点赞
1
收藏
0
