2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-1:g
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-1:g [2024/07/19 23:16] 11231123 |
2023-2024:teams:al_in_and_back_to_whk:24-nowcoder-1:g [2024/07/20 10:54] (当前版本) 11231123 |
||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 总时间复杂度就是 $O(n\log^2n)$ 。 | 总时间复杂度就是 $O(n\log^2n)$ 。 | ||
| - | ps:我感觉群里那个分析有问题吧，就是枚举次数大约是 $\sum{(r-l+1)/2p*p-(p-(r-l+1)\%p-1)}$ ，然后根据定义有 $(r-l+1) \ge 2p$ ，所以得到那个式子是不超过 $\sum{r-l+1-2p+1+(r-l+1)\%p}$ 的，但是我们并不知道 $\sum{(r-l+1)\%p}$ 是个什么数量级。 | ||
2023-2024/teams/al_in_and_back_to_whk/24-nowcoder-1/g.txt · 最后更改: 2024/07/20 10:54 由 11231123
