@[jingkongwanglimiaoa](/user/222578) 百度+bilibli真是个好东西~~
by YUN_0120 @ 2021-09-14 22:40:56
遇事不决请先问度娘，b站。
连知乎都很难接受这种问题 你觉得洛谷会接受么
by WanderingTrader @ 2021-09-14 22:42:33
@[gaoxinyun0120](/user/547298) @[wandering_trader](/user/270791)
我已经 bd 过了，可惜学校机房没得截图浏览记录
说这话前建议先自己 bd 一下，看能 bd 出来一个什么破玩意，第一项给我推出来的是 2012 CSP-s 的时空穿越题解，其它的更像一些随记，大概只有作者本人看得懂
之前好像有个嘲讽 bdfs 链接，我觉得它很不错，帮查对应内容。如果真能查到，可以嘲讽对方，如果不能查到，哈哈哈，哈哈，哈就别发了
B站是真的没有想到~~虽然我觉得在学校机房上B站不太好~~
关于知乎，我不理解什么叫 **连知乎都很难接受** ， [把知乎当什么了](https://www.zhihu.com/search?type=content&q=CSP-2020%20S%E5%88%9D%E8%B5%9B)
发挺长的回复，心平气和无意d人~~毕竟哪里不好就成我被d~~，来洛谷就是碰碰运气，看不惯请跳过
另外，如果你通过任何途径找到了能看（懂）的题解，欢迎拿它来打我脸，我不介意
以上 看到一位比一位更强的嘲讽语气，告诉自己保持心平气和
by jingkongwanglimiaoa @ 2021-09-14 23:13:58
心平气和不了了，莫名其妙生命又被浪费了一点
by jingkongwanglimiaoa @ 2021-09-14 23:17:55
大无语
by jingkongwanglimiaoa @ 2021-09-14 23:18:32
大无语
by jingkongwanglimiaoa @ 2021-09-14 23:18:43
大无语
by jingkongwanglimiaoa @ 2021-09-14 23:18:57
@[jingkongwanglimiaoa](/user/222578) [这个](https://www.cnblogs.com/Rainy7/p/csp-s-2020-first.html)，不知道有没有看过
by Utilokasteinn @ 2021-09-15 08:39:01
首先题目求的是区间第 $k$ 小值，~~常识可知时间复杂度是 $O(n)$ 的。~~
3. 不会
4. 因为是单调递减，第一次会将序列变成单调递增，之后就不会交换了，所以应该是 $O(n)$。
5. 首先最坏时间复杂度肯定是每次都 rand 到 $L$ 或者 $R$，时间复杂度显然 $O(n^2)$，故排除 B 和 D。又因为输入单调递增，所以平均复杂度为 $O(n)$。
6. 因为 $d_i$ 为同一个数，显然
```cpp
while (a < b && d[b] >= d[L])
--b;
```
每次都要将整个序列扫一遍，所以是 $O(n^2)$。
by Utilokasteinn @ 2021-09-15 08:55:36
@[еcho](/user/306049) 谢谢您，这个我看过，但大概算写的比较完整的随记？
我猜也是第 k 小的值（线索：k, 近似排序的代码,题目中的递减），但我比较想知道是怎么个程序逻辑实现的，因为这个程序逻辑不明白，导致我不理解复杂度怎么算，就是这样
谢谢您的解析！
by jingkongwanglimiaoa @ 2021-09-17 00:09:45