昨天晚上第二场：

A：

一开题以为是会考题。

给定 $n$ 个 $a,b$ 判断 $a$ 的平均值是否小于每一个 $k$。

因为 $a,b$ 范围为 $1e18$ ，而且要保留十二位小数，直接 long double 肯定不行，又因为 $n\leq 10^6$ 用 int128 模拟会 T。

正解是维护商和余数，模拟除法即可，刚好在 long long 范围内。

B：

比较水。

维护最大生成树，然后树剖 + lca 维护两点路径最小值，计算满足要求的车用树状数组维护即可。

C：

矩阵加速递推，比较好想，但是转移矩阵写起来很麻烦，前前后后敲了 30min。

今天上午：

A：

本来想写正解但是大部分时间都写 $B$ 去了，准备冲个暴力，然后我定睛一看：

诶🤓，是✌最喜欢的随机数据，而且时限 9s 随便冲。

耗得开始乱搞，30min 糊了个 sb 二分上去，check 里面长这样：

然后测本地 $n=50$ 的大样例过了，抱着试试的心态跑了 $n=2\times 10^5$ 的数据，一看 8s，感觉有戏。

这时候我发现二分 check 时用了几个 $abs$，感觉 $\max$ 可能更快，改完发现 9s 了，然后反向修改把所有 $\max-\min$ 都改成 $abs$，一测变 1s 了，开 O2 测了一发 0.5s。

人有点傻，但是一想是随机数据就释然了，感觉也就草 40 分，然后就跑去体育课了。

下午来了一看：

$n^3\log V$ 4e4 见过没，再一看：

嘿，你就凭 hack 来卡我十八。

然后卡了半小时常，加了一堆 b 优化，还是过不了，卡的过程中发现其实 Sub4 有 hack，但是没卡住我。

会去看了看 hack 数据，发现自己糖丸了，最后加了个特判：若 $x$ 的极差小于 $y$ 的极差，则交换所有点的 $x$ 和 $y$。

上午下楼的时候想到了，但是懒得跑回去加了，一测，过了，$n^3\log V$ 2e5 见过没 ，最慢点 3.9s，感觉上午亏大发了。

然后倒档回去，把上午代码就加了这一个优化交上去，2.2s，byd 我中间加的一车优化 p 用没有是吧。

然后打开

定睛一看：

byd 成榜一了，好好好，这么玩是吧。

正解也是二分，但是：

显然，对于三个点 $(A, B, C)$ ，如果存在一个边长为 mid 的正方形能覆盖这三个点，那把这个正方形选上一定不劣。因此问题可以表述为

• 对于每个点 $A$ ，判断是否存在三元组 $(A, B, C)$ ，满足存在边长为 mid 的正方形能同时覆盖 $A, B, C$ 。
  将平面分成 $mid \times mid$ 的块。注意到如果一块内有 3 个点，这一块内的点已经合法了。
  对于块内只有 $\leq 2$ 个点的块，对于其中每个点 $A$ ，枚举其周围 $(-1 \sim 1) \times(-1 \sim 1)$ 的块内所有点，这部分显然是均摊线性的。考虑以 $A$ 为角的正方形。这些正方形内都不能有超过 2 个点。

如果这样的话， $A$ 为中心的， $(2 \mathrm{mid}) \times(2 \mathrm{mid})$ 的正方形内的点数也是 $O(1)$ 的。直接 $O\left(c n t^{2}\right)$ 枚举所有点对判断即可。

实际上可以在 3s 左右通过。

实测可以在 2s 左右通过，不过也有老哥拿树状数组写的。

B：

这也是百家争鸣，解法一车，我用单调队列优化过的。

C：

根本不会多项式。

考虑分治，我们需要考虑维护跨区间贡献，可以用多项式多点求值解决，时间复杂度 $\mathcal O(n\log^2n)$。

拼尽全力无法战胜。

然后：

还有一种乱搞：考虑计算答案的平方，一次多点求值即可搞定。然而我们并不知道开出的二次剩余取哪一个，随机取一个，对于测试点数为 1 的子任务有 $1 / 2$ 的概率通过。