题解：P10068 [CCO2023] Line Town

· · 题解

另外那篇在写啥？？？

注：这篇题解主要负责补充实现以及详细讲解“贡献可以树状数组简单计算”，默认大家已经会了原题解中“启示我们按照绝对值大小填数”前面的部分。

下面称所有绝对值相同的数为一类，符号相同且绝对值相同的数为一组，朝左和朝右分别表示这个数要放到当前考虑区间的最左端和最右端。

对于同一类数，我们枚举要往左边放 i 个数。

这个时候注意我们需要满足从前面贪心选择 i 个数和从后面贪心选择 l-i 个数（l 是这一类的数的个数）拼起来能够恰好对应所有数，因为有可能会出现同一个数从前面贪心和从后面贪心同时被选到的情况。

之后我们还要考虑贡献分为哪些。画出上下两个数轴，把每一个点的起点和终点在上面和下面画出来并连边，那么任意两个数会产生贡献当且仅当他们的线段相交。答案显然是两两贡献之和。

我们把相交情况分成以下三种：

  1. 其中一个属于当前考虑的类，另一个属于其它类。
  2. 两个都属于其它类，但是在不同组。
  3. 两个都属于同组。

第一个贡献是容易计算的： 考虑最开始把每个数都放入树状数组，每次把当前类的数全都从树状数组删除然后计算树状数组中剩余的数（这些数的绝对值会比当前考虑的更小）和这一类的所有数的贡献。 对于一个数 p，假设他要移到左边，那么树状数组中所有 <p 的数都会与它相交（因为这里的数最初都在 p 左边，结束之后都在 p 右边）。如果要移到右边，那么树状数组中所有 >p 的数都会与它相交。这些直接存下来即可。

同类不同组的贡献可以在枚举左右放的数的个数的时候动态更新。最初所有数都是朝右，之后按顺序每次把一个数改成朝左。 用两个树状数组代表两个方向的数都有哪些。当一个数 p 从朝右变成朝左的时候，原本他会与 >p 的朝左的数相交，这一部分贡献需要减掉。变成朝左时他会与 <p 的朝右的数相交，需要再加上这一部分的贡献。

最后我们需要计算同组内的贡献以及选择前 / 后 i 个数的时候的选择情况。选择情况是指每组内部排序之后贪心选择一些数之后两组各考虑到了哪个位置。 这里只写从前往后贪心的情况，从后往前是等价的。 直接枚举当前从前往后放了 i 个数，考虑此时的状态和内部相交的贡献。根据当前格子所需要的组贪心选数，假设此时选了 p。那么在 p 之前选的所有数的终点都会在它左边，所以所有 >p 的数都会与其相交，再用一个树状数组记录即可。

具体的写法可以自己感受。