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

P2572 [SCOI2010] 序列操作

金珂拉 @ 2021-08-25 21:15:48

序列操作AC记录

这玩意真的离谱……

题解里面有暴力 O(\min(N,Q)\times Q) 珂朵莉树,然后我按照我的习惯调整成了复杂度正确的O(n\sqrt n) 的定期重构链表式珂朵莉之后成功过了()

但是因为操作4处理两端多余部分和进行split操作的时候依旧搞一层静态区间最小值,所以复杂度显然不可能比线段树好,也没有珂朵莉树在随机数据下的良好特性,而且码量也大了一坨……


by 金珂拉 @ 2021-10-19 20:59:11

@某珂学的超OIer 确实不是,直接合并相同的值是不行的,而是要把整棵树合并起来(换句话说实际上就是用类似指针实现的块状链表)


by 某珂学的超OIer @ 2021-10-19 21:13:02

@金珂拉 懂了懂了,谢谢奆佬


by 猫猬兽 @ 2021-10-19 21:54:41

@peterwuyihong 论暴力的强大,O(n^2)能过


上一页 |