关于用珂朵莉树维护【模板】文艺平衡树 的一个设想
  • 板块学术版
  • 楼主金珂拉
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/8/22 18:43
  • 上次更新2023/11/4 09:27:44
查看原帖
关于用珂朵莉树维护【模板】文艺平衡树 的一个设想
147670
金珂拉楼主2021/8/22 18:43

因为珂朵莉树的实际复杂度是与区间数挂钩的,而因为每次进行一个操作就会让两个端点位置的块分裂,所以总块数可以看成 min(n,q×2)\min(n,q\times 2)

如果用链表维护珂朵莉树,则时间复杂度为 O(q×min(n,q))O(q\times min(n,q)) (用平衡树维护则是qlogq,但是因为在文艺平衡树中需要暴力维护块的翻转所以不行)

而文艺平衡树中,显然对操作较少的情况,我们只要每次把连续的数合并成一块并且打上标记,就可以用珂朵莉树做到 O(q2)O(q^2) 的复杂度。

所以可以考虑把操作分块之后,每块内用珂朵莉树维护,维护完之后,合并两个询问块相当于把两个双射函数合并起来,复杂度是O(n)O(n), 所以最终复杂度为

O(Q/T×(T2+N))=O(QT+NQ/T)O(Q/T\times (T^2+N) )=O(QT+NQ/T)

显然取T=n1/2T= n^{1/2} 时最优,复杂度为 O(Q×n1/2)O(Q \times n^{1/2})

求大佬们看看这样搞对吗?

2021/8/22 18:43
加载中...