学习笔记：偏序问题

· · 个人记录

前置知识：简单的树状数组/线段树，离散化

1 一维偏序

问题：有 n 个数，现有 q 组询问，每组询问给定 x，求小于 x 的数的数量。

当然是水题，随便乱搞。比如说把数据排序然后二分查找

当然，不是为了介绍比较简单的做法，而是为二维偏序做铺垫。

一个比较麻烦的做法是，先把数据离散化，此时每个数不超过 n。

然后维护一个桶。这个时候每个数对右边的询问有1的贡献，显然答案就是前缀和。

你可以把前缀和直接做出来，这样只需 O(1) 就可以回答任何询问了。

然而还有一个更麻烦的做法是用数据结构（树状数组），每次加入一个原来的数，然后前缀和就是区间查询。每次询问时间复杂度 O(\log n)。但是支持修改了。这一特性将在扫描线求二维偏序的时候起重要作用。

2 二维偏序

问题：平面直角坐标系里有 n 个点 (x_i,y_i)，现有 q 组询问，每组询问给定 x,y，求横坐标小于 x 且纵坐标小于 y 的点的数量。（即位于 (x,y) 左下方的点的个数。当然端点开闭不限）

显然，暴力每次询问 $O(n)

对于这个问题，有两种离线做法：扫描线+数据结构和cdq

2.1 扫描线+数据结构

以两个约束都是小于等于为例。（当然小于大于随便，开闭随便，做法差不多）

先考虑 x_i,y_i 与 n 同阶的情况，因为可以通过离散化转化为同阶的情况。

考虑把询问离线下来，然后按照 x 从小到大排序。所有点也按 x 从小到大排序。

现在考虑有一根竖直的线，从左往右扫过所有点和询问。在扫到一个询问的时候才回答。

显然每一个询问只和线左边的点有关，并且只要在线左边就满足横坐标的约束（因为扫到一个询问的时候才回答，线和询问横坐标一样。所有对一个询问有贡献的点都在询问左边，和在线左边是等价的），只需要考虑纵坐标的约束关系。

这个时候就转化成一个带修改的一维偏序：y 代表数的大小，而 x 变成一个操作的时间轴。还是对纵坐标维护一个桶。每次扫到一个点的时候，就把这个点加进去，然后回答询问就是求前缀和。还是使用树状数组。就做完了。

接下来可以先看使用例。

2.2 cdq（待补）

由下面的使用例已经说过了，逆序对就是二维偏序，事实上，归并排序求逆序对就是cdq的思想，只不过板子题里就求了一个和

2.3 使用例

二维偏序问题的关键在于如何将一个问题转化为二维偏序。

2.3.0 带修改的一维偏序

题意如上

把操作的序号看成 x_i，数的大小看成 y_i，询问 (x,y) ，求的是 x_i<x 且 y_i<y 的点的个数。所以这是二维偏序。

2.3.1 二维偏序的变种

题意：平面直角坐标系里有 n 个点 (x_i,y_i)，现有 q 组询问，每组询问给定 x,y1,y2，求横坐标小于 x 且纵坐标在 y1,y2 之间的点的数量。

做法一样，只需把前缀和变成 [y1,y2] 的区间查询即可。（想一想，为什么）

2.3.2 P1908 逆序对

题意：给定一个序列，求逆序对总数。

把 i 看成 x_i，a_i 看成 y_i，询问 (x,y) ，求的是 x_i<x 且 y_i>y 的点的个数。答案是所有 1\le i \le n 询问 (i,a_i) 结果的和。所以这是二维偏序。

2.3.3 CF1042D

题意：有一个长度为 n 的序列 a，和一个数 t，求有多少个区间 [l,r] 满足 a_l+a_{l+1}+...+a_{r} <t 且 l\le r。

题目和区间和有关，考虑转化为前缀和，设前缀和是 s_i(s_0=0)。那么 t>\sum_{i=l}^r a_i=s_r-s_{l-1}。这等价于 s_{l-1}>s_r-t。

把 i 看成 x_i，s_{i-1} 看成 y_i，询问 (x,y) ，求的是 x_i\le x 且 y_i>y 的点的个数。答案是所有 1\le i \le n 询问 (i,s_r-t) 结果的和。所以这还是二维偏序。

2.3.4 P2163 [SHOI2007] 园丁的烦恼

题意：给定二维平面上若干个点，每次询问求一个矩形内的点的数量。

之前提到了二维偏序的答案其实是一个二维前缀和。所以把一个询问按矩形四个顶点拆成四个询问，每个询问的答案就是顶点坐标的二维前缀和，用上面的方法把四个询问答案求出来直接容斥即可。

2.3.5 P8844 [传智杯 #4 初赛] 小卡与落叶

题意：给定一棵树，询问编号 x 子树内深度 \ge y 的结点个数。

注意到，一个子树的dfs序是连续的，所以dfs预处理点的深度 dep[i]、dfs序 dfn[i]，和任一结点 i 子树所管辖的dfs序范围 l[i],r[i]。

把 dep[i] 看成 x_i，dfn[i] 看成 y_i，询问 x ，求的是 x_i\ge y 且 l[x]\le y_i\le r[x] 的点的个数。所以这还是二维偏序。虽然极度抽象

2.3.6 P1972 [SDOI2009] HH的项链

题意：给定数列，询问区间 [l,r] 不同数的个数。

没有错。区间染色数是个带修改一维偏序。首先把询问按照右端点排序。只有下标小于 r 的位置才有可能有贡献。这就是偏序。

考虑从左往右扫 r。每次加入一个数的时候，看左边有没有相同的数（这个可以预处理）。如果没有，直接加入。如果有，在 l 往左移动的过程中，右边的数一定先包含进区间里，所以左边那个数一定没有贡献（无论右边那个数有没有贡献），这个时候就把左边的那个数删除掉。这样 [l,r] 内不同数的个数就是其区间和。

带修改一维偏序和二维偏序是同一个东西。

3 三维偏序（待补）