二维偏序问题与树状数组

二维偏序问题 #

设 $R$ 是集合 $A$ 上的一个二元关系, 若 $R$ 满足:

• 自反性: 对$\forall x\in A$ , 有 $xRx$;
• 反对称性: 对$\forall x,y\in A$ , 若 $xRy$ , 且 $yRx$ , 则有 $x=y$ .
• 传递性: 对$\forall x,y,z\in A$, 若 $xRy$ , 且 $yRz$ , 则有 $xRz$ .

则称 $R$ 是 $A$ 上的一个偏序关系. 一个典型的二维偏序问题如下: 输入二维坐标下一系列不相同的点, 对每个点, 输出横纵坐标均小于它的点的个数.

一般处理方法 #

二维偏序问题涉及数组维护和区间查询两个方面, 考虑利用树状数组来进行处理. 接收数据后, 我们将数据按照一个维度排好序, 这时候考虑其第二个维度即可. 例如, 将平面上的点按照横坐标从小到大排序, 此时根据横坐标依次处理点只需要考虑排在其位置之前的点的纵坐标即可. 对每个点, 我们按照如下流程处理:

• 读取纵坐标
• 输出其前缀和
• 更新树状数组