有能卡掉的数据吗？
by xzf_200906 @ 2022-01-17 22:15:22
> 2019.12.12 更新数据，放宽时限，现在不再卡常了。
by Skykguj @ 2022-01-17 22:19:47
但是这份代码的最坏时间复杂度应该是$O(n^2)$ 的吧？
by xzf_200906 @ 2022-01-17 22:25:07
草，这做法一时不会卡
by zhy137036 @ 2022-01-17 22:42:30
@[xzf_200906](/user/529492) 您这应该是 $O(n)$ 的算法吧
by Z_301 @ 2022-02-28 10:25:18
@[xzf_200906](/user/529492)
对于每一个 $a_i$ ，如果：
1. $a_i\le a_{i+1}\ O(1)$
2. $a_i>a_{i+1}$，则求解需要一定的时间，但如果前面还有一个 $a_j>a_i$ ，则跳的时候会直接跳过 $a_i$ 和 $f_{a_i}$ 之间的数，也就是说对于每个 $i$ , $f_i$ 只会跳一次，复杂度均摊 $ O(1)$
所以原程序总复杂度是 $O(n)$的
写的不太标准，将就着看吧qwq
by Z_301 @ 2022-02-28 10:45:18