2020.11.2

【ZROI】联赛集训Day16

A

显然每组的次数可以单独算，且 $a_i \leq 2$ 的时候不可分。

然后可以枚举每个数 $i$ 分成哪两个数，取最优可以打出一个表，可以观察到,$max_i = i-2, min_i = \lfloor \frac i 2 \rfloor$。

B

根据样例可以找到规律：

特判掉 $n \leq 4$。

然后可以发现整大正方形会被放下的点划分成若干个小正方形，每次会先放在小正方形的中心，再放在边上。

但是本题的精度要求非常高，看起来需要手写高精度小数，但是实际上只需要支持除以 $2$ 的操作，因此只需要维护乘以 $5$，再除以 $10$ 即可。

C

答案显然一定会卡到个矩形上，因此考虑对于 $a_i$ 可以更新哪些位置的答案。

设 $l_i, r_i$ 表示左右第一个比 $a_i$ 小的数的位置。

• 对于 $j \in [i, r_i)$，可以用 $a_i (j-l_i)$ 更新答案。

• 对于 $j \in [r_i, n]$，可以用 $a_i(r_i-l_i-1)$ 更新答案。

  这两个更新方式都可以用李超树维护。