二维偏序

二维偏序

本文瞎胡

众所周知,逆序对是经典的二维偏序问题 ( 反正我一开始是不知道 ) .

我认为二维偏序问题可以概括为 (:) 双约束条件的元素统计问题.

而逆序对的定义是 (i<j) 且 (v_i>v_j) 的一对数字称为一对逆序对.

双约束分别是位置和权值.

一般考虑先定一维,再用某种方法去维护第二维.

例如,逆序对中,我们需要定第一维 (:) 位置 .

而这是输入就有的,所以不需额外固定.

再看另一个例子 (:) 对于二维平面上的一些点 ((x_i,y_i)) , 满足在一条直线 (x+y=c) 右侧且在另一条直线 (x=t) 左侧的点有多少个的问题.

可以发现,这相当于是对于一些点 ((x_i,y_i)) 统计有多少个点满足 (x+y<c) 且 (x<t) .

这是经典的二维数点问题,如果给定的区域是矩形,则可以用二维线段树或二维树状数组完成,(缺点,难写难调).

逆序对的二维偏序实现方式是怎样的呢 (?)

定第一维 (:) 从前向后考虑,这样每次只需考虑已经处理过的元素.

查询第二维 (:) 用权值树状数组维护一个权值的前缀和 , 即维护小于当前位置权值的点有多少个.(因为树状数组本身即是前缀形式,所以和一般的树状数组写法相同).

合并 (:) 从前向后把元素插入权值树状数组,每次查询从当前元素到最大元素的权值个数累加答案即可.

这样统计答案为什么是对的 (?) 因为在当前元素前面的元素一定已经被插入了树状数组,此时查询从当前权值到最大权值的权值个数即是对于当前位置 (j) 满足 (i<j) 且 (v_i>v_j) 的元素个数.

另一个问题二维数点如何实现呢 (?)

先按照显然的易处理的第二维 (x<t) 排序,再考虑用权值树状数组去维护第二维,这里的权值显然定义为 (x+y) , 直接查询前缀和即可.

当然,以上用到权值树状数组的地方完全可以使用权值线段树代替 ( 如果时间卡的不紧的话 ) , 之所以选择树状数组,是因为树状数组好写好调,常数小,也省空间.