社区讨论

论定期重构珂朵莉树的强大(

P2572[SCOI2010] 序列操作参与者 7已保存回复 13

讨论操作

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

当前回复
13 条
当前快照
1 份
快照标识符
@lobw7sok
此快照首次捕获于
2023/10/30 03:57
2 年前
此快照最后确认于
2023/11/04 09:01
2 年前
查看原帖
这玩意真的离谱……
题解里面有暴力 O(min(N,Q)×Q)O(\min(N,Q)\times Q) 珂朵莉树,然后我按照我的习惯调整成了复杂度正确的O(nn)O(n\sqrt n) 的定期重构链表式珂朵莉之后成功过了()
但是因为操作4处理两端多余部分和进行split操作的时候依旧搞一层静态区间最小值,所以复杂度显然不可能比线段树好,也没有珂朵莉树在随机数据下的良好特性,而且码量也大了一坨……

回复

13 条回复,欢迎继续交流。

正在加载回复...