2022/04/13 做题记录

Sereja and Arcs

设出现次数 $>\sqrt{n}$ 的颜色为“大颜色”，剩下的为“小颜色”，小-小 的答案因为相同小颜色的点对最多只有 $n \sqrt n$ 个所以可以直接扫描线 + 树状数组，注意去除四个颜色都相同的情况。

对于 小-大 和 大-大 的答案我们枚举右边那种大颜色时什么，设它出现次数的前缀和数组为 sum。

答案就是 $\sum_{i=1}^n\sum_{j=1}^{i-1}(sum_i-sum_j)sum_j$，其中 i,j 颜色相同且不为我们枚举的大颜色，对于每一种颜色开一个数组记录 $\sum sum_j$ 和 $\sum sum_j^2$ 就行，至于大-小的答案我们反过来枚举然后保证 i,j 不为大颜色就行。

code: /code/2022.4.13/ac10501.cpp

bzoj 1455

左偏树模版。

code: /code/2022.4.13/bz1455.cpp

P3320

实际上就是求这些点建出来的虚树的边权和的2倍，而一个树的边权和的两倍可以用 dfs 序上两两相邻的点之间的距离和来表示，而虚树的 dfs 序一定是原树的子序列（证明大概就是按原树的 dfs 序列在虚树上走，遇到不存在的就跳过，也一定是一个合法的 dfs 序），之后 set 维护两两之间的距离和就行（注意要加最后一个点和第一个点之间的距离）。

code: /code/2022.4.13/P3320.cpp

P4103

建完虚树后之间在树上 dp，每条路径在 lca 处统计贡献。

不要写换根 dp，特别不好写！

code: /code/2022.4.13/P4103.cpp

P4331

首先可以把每个 $a_i$ 减去 $i$，最后把每个 $b_i$ 加上 $i$，这样我们只需要 $b_i$ 单调不降。

对于一个单调下降的 a ，b 一定是取 a 的中位数最优

因为把一个序列看成坐标系上一些连续的线段，那么 b 与 a 没有交点一定不优，如果有交点因为 b 单调不降所以一定把所有数都调整为交点的值最优，而交点一定去中位数最优。

但是对于每个单调下降区间都取中位数不一定合法，所以我们有时后需要将两个区间合并取大区间的中位数，可以类似的证明这样一定是最优的。

而合并两个区间可以利用左偏树维护所有小于等于中位数的数，合并区间的时候不断弹出最大值即可（实际上，这种做法对于合并任意两个区间是错误的，但由于我们是不断的从大到小的合并单调递减区间，正确性可以有保障）。

code: /code/2022.4.13/P4331.cpp