在本题题解里面没有找到任何认真分析复杂度的/kk
by rui_er @ 2023-01-14 17:12:15
谔，我也是昨天刚写的。
$10^{18}$ 开平方下取整 $6$ 次就可以得到 $1$。
所以这题复杂度存在一个常数（?）
by Ap0calyptic_ @ 2023-01-14 17:20:40
@[__haimo__](/user/676921) 我知道开根号次数是 $\Theta(\log\log w)$，我就是想问一下本题的复杂度是 $\Theta(n\log n\log\log w+m\log n)$ 还是 $\Theta(n\log n+n\log\log w+m\log n)$。我不是很会势能分析，最近突然想到了这题，然后发现我不会分析复杂度了，题解里也没有说。
by rui_er @ 2023-01-14 17:22:51
而且这题跟你说的那个还不完全一样，按你说的那个显然直接全堆一个点上就是 Slogn，但是这题显然没法全堆一个点上...
by Sol1 @ 2023-01-14 17:32:10
emm 怎么删了/kel
by rui_er @ 2023-01-14 17:35:40
@[rui_er](/user/122461) 定义势能函数为不全为 $0/1$ 的下标 $s$ 的和。显然每次操作的代价不超过 $O(1)$ 加势能函数的差值的 $\log n$ 倍，所以可以得到 $O(q+S\log n)$ 的 bound.
分析错了欢迎来喷 /kel
by esquigybcu @ 2023-01-14 17:39:56
想了一下，$q\le S$ 的话这个 bound 是紧的：你对 $[1,1]$ 做 $s_1$ 次，对 $[2,2]$ 做 $s_2$ 次，以此类推。
by esquigybcu @ 2023-01-14 17:41:54
@[esquigybcu](/user/384214) 谢谢，我理解理解
by rui_er @ 2023-01-14 17:42:38