一个元环,在时刻从任意一个位置出发,每一秒可以选择往后或者留在原地
每个点有个参数,当你走到的时间时就可以把标记
求把整个环上的点都标记最小需要多长时间,需要支持修改,强制在线
Links
Solution
感性考虑一下可以发现最优方案肯定是现在所选起点停留足够长时间再往后直接走一圈
破环为链后实际上是求
可以转化成
设,化简得到
考虑用线段树维护这个东西
对于当前根对应的区间,考虑如何维护
定义计算
那么有 (其中表示区间最大值)
考虑如何计算
可以发现,若,则就等于左儿子的答案,于是只需要递归右儿子
否则就等于右儿子的答案,此时只需要递归左儿子
(以上两个结论都很好证明,直接带到原式中观察一下就能发现是对的)
那么就能在的时间内求出的值了
总复杂度
Code
1 |
|
Debug
- 89L, 97L:
n<<1
写成1<<n
。。。