推土机

千花秋雨 · 2024-11-27 08:52:51 · 题解

前置知识：小白逛公园。

样例解释：样例说明。

思路：

• 假设平行线的斜率已确定。从上往下扫，把每个点按扫到的时间顺序存入线段树，答案等价于求最大子段和。

• 先把两平行线重合穿过一个给定点，两平行线重合但什么也不穿过的情况算上。

• 有这样一个集合 S，包含了以下两种直线。

  1. 一条直线穿过两个给定点。

  2. 只穿过一个给定点。

• 根据样例解释，可以发现除去特判的情况外，答案一定可以由集合 S 中的两条平行线围成。因此枚举两两点预处理直线斜率。

• 当平行线斜率改变时，两点在线段树上的顺序（即被平行线扫到的先后顺序）才会变。两点间的顺序只变一次，故总变化次数是 \mathcal {O(n^2)} 的。

• 因此我们将平行线进行极角排序 ^{\clubsuit} 。然后计算过程中不停交换两两点的位置，这样的排序方式可以保证不重不漏，两点间的顺序刚好变一次（你可以将字母 A,B,C,\cdots 围成一圈，两两交换，看看是不是不重不漏）。

极角排序 ^{\clubsuit} ：把平面上的一些点按照一选定的中心点（不一定是给定点）排成顺（逆）时针。这篇(详细) 和 这篇(简洁) 都值得一看。

时间复杂度：\mathcal{O(n^{2}\log n)}。

代码中变量及函数意义的解释：

代码：CODE。

• 结构体 point：保存一个点的横纵坐标。

• 数组 p：当前点在原序列（输入序列）中是第几个。

• 结构体 a：输入的点集，p,w 分别维护坐标、权值。

• 结构体 b：p 维护两点坐标的差，x,y 代表 p 中的坐标是序列 a 中哪两点做差得来的（注意这里的 x,y 是 a 排序后的下标）。

线段树维护最大子段和部分不加赘述，但是要注意更新时与 0 取最大值，如果贡献为负数的话，我们当然可以不选这样的点。

以下是实现极角排序的函数，学习向量后会更加便于理解。

• 函数 cmp：把 a 中的横坐标小的点排到前面，横坐标一样大就把纵坐标小的排到前面。

• 函数 k：用于对极角排序而进行的计算。你可以理解为斜率比较函数。k 值为负数时，前一条线斜率更大。k 值为 0 时，斜率一样大。k 值为正数时，后一条线斜率更大。

• 函数 cmp2：把所有两两点组成的直线按照斜率从小到大排序。一样大就把横坐标小的放前面，横坐标也一样就把纵坐标小的放前面。

如果你不明白为什么这样可以让直线按照斜率从小到大排序，请看这里的一些补充说明。

（这里很多排序是个性化的，你也可以按照其它顺序排）

常见错误：调试请查看。

本题解的 LaTex 可自取。