Sol 1

任取一个点 $u$ 跑最短路，设离它最远的点的点距离为 $dis_u$，则：

所以 $\frac 12 d(G)\le dis_u$ 已经满足了，只需要满足 $dis_u\le 2d(G)$ 就行了，可以放缩为一个更强的条件：

二分一下找到第一个不满足条件的时间就行了，每次 $dis$ 都会除以二，所以只需要二分 $\log n$ 次。

Sol 2

对于 $|C_i-C_{i+1}|$，把 $C_i$ 排序，那么相邻部分的贡献的最大值就是 $2\ 4\ 6\ 6\ 4\ 2$，或者 $2\ 4 \ 6\ 4 \ 2$，那么枚举中间值，维护两侧的前 $\frac k2$ 大的贡献即可。

超，是不是看成加上 $\sum|C_i-C_{i+1}|$ 了。

Sol 3

事实上，记 $S_r$ 表示以 $r$ 结尾的区间的不同绝对众数的数量，那么 $\sum |S_r|\sim O(n)$。考虑每个数作为绝对众数出现的区间，记它为 $+1$，别的是 $-1$，那么能作为 $r$ 的只有“非前缀最小值”，而非前缀最小值的数量同阶于 $+1$ 数量，总共也就只有 $O(n)$ 级别；可能作为左端点出现的位置的量级同理。所以可以 $O(n)$ 维护！

Sol 4

点减边减四边形个数等于连通块数，做完了。

更为有广泛性的做法：选取代表元。维护区间内可以成为代表元的个数，如果一个点存在一个向比它更小的路径，那么它也不能成为代表点，容斥每个点不能够成为代表点的所有情况，设情况数为 $c$，则复杂度为 $2^c$。

Sol 5

wqs 二分，然后在括号树上树形 dp，用斜率优化维护树形 dp 的过程。

Sol 17

如果两个数关于 $0$ 对称，那么它们到达 $0$ 的时间一定完全一致，所以我们可以把数轴对称位置的数先合并，只保留两侧中比较多的那一侧的所有元素；这样做的话，有元素的是一个区间，并且每次是把一个前缀或者一个后缀翻进去，这样总复杂度是对的。

Sol 8

从大到小 dp，暴力存下所有剩下的数前面有多少个数。

Sol 6

遇到问题不会做不应该发呆，也许应该去考虑这个问题的某一个截面。

这题中，分别考虑每一个粒子对撞器，首先求出其最小循环节答案不劣。在它左边放一个左挡板，右边放一个右挡板，一定是等价的，因为右边会走回来，左边也会走回来，不妨看作是直接返回的挡板；第一次一定是从左边来，暴力模拟一下绕最多两圈回去时，向左走了 $x$ 次，向右走了 $y$ 次，设在最终的循环节中，向左走了 $a$ 步，向右走了 $b$ 次，那么一定有 $\frac xy=\frac ab$，并且 $i-1$ 向右的次数要等于 $i$ 向左的次数，那么就可以贪心了。

哦对，这题等价于要回到初始状态的原因是：状态的下一个状态是确定的，上一个状态是可以倒推的，所以是一个环，而不是 $\rho$。

Sol 10

根号分治即可。

Sol 19

保留 $a$ 和 $b$ 的凸包并闵可夫斯基和，调整法就能证了。