@[违规用户名684254](/user/684254) 我不认为权值线段树能代替平衡树
by opHJY2023 @ 2023-02-23 11:09:53
可以,但不能做区间reverse和序列中间插入
by KellyFrog @ 2023-02-23 11:14:01
不过这道题应该主席树可以过...
by opHJY2023 @ 2023-02-23 11:15:58
@[_HJY2022](/user/236867)
事实上,这题是离线的。我可以全部读入,再离散化,然后和动态主席树一样去做。
+ 1.2.4不必多说
+ 3.二分
+ 5.6 求出x的排名k,在查询整体第k-1或k+1大
整体时间复杂度为 $O(nlog^3n)$
by Rain_chr @ 2023-02-23 11:17:15
算出来之后感觉时间不对啊 (3e9)
by Rain_chr @ 2023-02-23 11:18:51
@[违规用户名684254](/user/684254) 这是单 $\log$ 的。
by Usada_Pekora @ 2023-02-23 11:19:14
@[违规用户名684254](/user/684254) 没意义...
你做板子题不写对应算法干吗...
by opHJY2023 @ 2023-02-23 11:20:20
@[Usada_Pekora](/user/434929) 动态主席树就是双 $log$ , 还要二分排名不就是 三 $log$ 吗
by Rain_chr @ 2023-02-23 11:21:09
@[违规用户名684254](/user/684254) 而且如果离线的话都没有写可持久化的意义吧...
by opHJY2023 @ 2023-02-23 11:21:54
@[_HJY2022](/user/236867)
板子题不一定要写对应算法啊……这只是在讨论可能性
by Rain_chr @ 2023-02-23 11:22:07