首先O(n1/3)的复杂度,容易想到可以进行块状链表嵌套
外层维护一个块状链表,内层再维护一个。
但是显然如果是普通的块状链表,肯定无法实现,因为块状链表的每块块长是需要稳定的。
我们以线段树为例:
内部维护一个链表,链表上的每一个点有一个三元组(l,r,tag),其意义类似于线段树的节点,l,r
表示这个节点所代表的区间的左右端点,而tag相当于懒标记。开始只有一个节点(1,n,0)表示未经过修改的原数组
在链表中,可以通过split(也就是将一个节点分裂成两个节点)来取出一个区间
容易发现,这个东西不需要维护块长,因为我们在这上面修改的时候,对于两端,比如说如果修是l,r,tag2,左端是(l1,r1,tag1),而且l1<l<r1 那修改的时候不是像块状链表/分块一样是暴力维护,而是用O(1)的时间拆成(l1,l−1,tag1)和(l,r1,tag1+tag2)两个节点。
而维护这个东西显然不需要像块状链表那样要求每块的数字小于根号之类的问题,所以也不需要移动多出来的节点,所以把这个链表作为内层链表,可以避免维护块长而导致的复杂度错误。
外层链表则使用普通的块状链表来优化复杂度。
但是你们肯定发现了一个问题:这个东西不像块状链表一样可以merge这类的操作,操作数多了之后块内肯定一塌糊涂。
所以我们可以定期重构一下:每经过一定的时间将懒标记清空,更新原数组以及其前缀和数组(或者如果用来写排名就建主席树。这个东西的最大优势就是可以把大多动态问题以增加一个根号的代价变成静态问题,比如说把线段树变成前缀和,把动态区间最小值用四毛子维护之类的事情。)。
设内层的链表内节点数超过T1就清空懒标记,外层块状链表的块长为T2
复杂度:O(mT2+mT1/T2+m/T1×n)
显然取T1=n2/3,T2=n1/3时候最优,复杂度为 mn1/3
评测记录:线段树1 200毫秒