社区讨论

求助 lhx 序列带权分治

2026/02/10 12:01P10165[DTCPC 2024] 人赢的跳棋参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复: 2 条
当前快照: 1 份
快照标识符: @mlhy7802
此快照首次捕获于: 2026/02/11 19:30
此快照最后确认于: 2026/02/11 20:20

题解复杂度是

\log_{\varphi}

吗？

对于 lhx 的栈维护，如果没写错是：

依次加入 $i=1,2,3,\cdots,n$ 。
重复执行：对于栈顶优先级 $r_{x},r_{y}<r_i$ ，那么合并 $x,y$ ，加入栈。
检查栈顶 $r_{y}\le r_i$ ，如果是的话合并 $y,i$ ，加入到栈。否则直接加入 $r_i$ 。

最后重复合并栈顶。

那么举个简单的例子，1,1,1,1,1,1,...。对于这个，是不是会合成 2,2,2,2,...，最后依次合并栈顶，我们得到一个很深的分治树。

我对于做法的理解哪里出问题了？

回复

共 2 条回复，欢迎继续交流。

正在加载回复...