自动搬运

查看原文

来自洛谷，原作者为

	Autumn_Rain 机惨我的人妈炸了

搬运于2025-08-24 22:59:45，当前版本为作者最后更新于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 可自取。