2023 winter training short round #2

rk 13

A,B,C 花的时间都太长了，导致后面太赶。

A 写了一个垃圾分讨+二分，边界太多用了 25mins 才过。

当时刚睡醒，题都没读懂。

B 构造又错在了一个细节上面，其实是自己写的太丑了导致细节很多。

a=b 的条件没处理好，调了半天。

然后开 C ，一开始又读错题了。

对着式子看了半天也没思路，其实移项一下就能发现让差形成剩余系了。

写完 C 不到1h，直接开了 E ，随便推了推发现是个最小化 $ax+by$ 的东西。

想到了这是扩欧那个方程，然后就去写。中间exgcd还写错了

最后不到 30min 开了 F ，一眼单调性然后有个区间加。

按理说2个log应该用个树状数组的，但是没时间了直接码了线段树

主要是动态开点的树状数组确实没写过

最后结束也没调完。

卡了我的是 1 0 1 0 这个test，都相等的时候没处理好

应该在 0 和 1e9 的时候加个特判

简单总结一下，还是读题、思考有点着急。

应该把思路理得很清楚了再写代码

有思路不应该着急写，反复推一下看看是不是假的

不该猜的时候不要瞎猜结论

注意细节

D

放在这里了。

F

不难发现，结束温度随初始温度单增（非严格）

那么对于第 i 天的温度 $T_i$ ，我们可以通过二分找到两个点 $p_1,p_2$ 。

使得当初始温度 $T_0\in[0,p_1]$ 时，第 i 天的温度小于 $T_i$。

$T_0\in[p_2,10^9]$ 时，第 i 天的温度大于 $T_i$。

建一棵动开线段树，每个节点维护初始温度在 $[l,r]$ 时的变化量。

进行区间+1/-1，就可以得到任意初始温度经过 i 天后的温度了。