因为珂朵莉树的实际复杂度是与区间数挂钩的,而因为每次进行一个操作就会让两个端点位置的块分裂,所以总块数可以看成 min(n,q×2)
如果用链表维护珂朵莉树,则时间复杂度为 O(q×min(n,q)) (用平衡树维护则是qlogq,但是因为在文艺平衡树中需要暴力维护块的翻转所以不行)
而文艺平衡树中,显然对操作较少的情况,我们只要每次把连续的数合并成一块并且打上标记,就可以用珂朵莉树做到 O(q2) 的复杂度。
所以可以考虑把操作分块之后,每块内用珂朵莉树维护,维护完之后,合并两个询问块相当于把两个双射函数合并起来,复杂度是O(n), 所以最终复杂度为
O(Q/T×(T2+N))=O(QT+NQ/T)
显然取T=n1/2 时最优,复杂度为 O(Q×n1/2)
求大佬们看看这样搞对吗?