0x40 数据结构进阶

桃扇骨 2021-10-19 03:31 144阅读 0赞

### [Can you answer these queries I][] ###

区间最大子段和模板题。见下

### [Can you answer these queries III][] ###

考虑子段和的三种组成方式：

*  全在左儿子里
 *  全在右儿子里
 *  两边都有

可以想到维护一棵线段树，每个节点有四个值\\(sum,lmax,rmax,dmax\\)。

sum为区间和，lmax为从区间左端点开始的最大子段和，rmax表示在区间右端点结束的最大子段和，dmax则表示区间最大子段和。

显然有

\\(lmax=max(ls.lmax,ls.sum+rs.lmax)\\)

\\(rmax=max(rs.rmax,rs.sum+ls.rmax)\\)

\\(dmax=max(ls.dmax,rs.dmax,ls.rmax+rs.lmax)\\)

### [Can you answer these queries IV][] ###

考虑开方操作，易知极限数据最多被修改六次，因此可以考虑暴力解决。

额外维护一个区间最大值，当最大值为1的时候就可以不用修改该区间了。

### [Can you answer these queries V][] ###

终于A了，有一个细节需要注意（附在后面）。

分情况讨论：

*  如果两个区间互相分离，显然是前一个区间的右侧+中间的和+后一个区间的左侧。
 *  如果两个区间有交集，那么有三种情况：
    
     *  起始点在L2左侧：\[L1,L2\]的右侧+\[L2,R2\]的左侧。 ------ \*
     *  起始点在L2右侧：\[L1,R1\]的右侧+\[R1,R2\]的左侧。
     *  跨越没有前两个那么大，就在\[L2,R1\]之间。

注意：在处理（\*）这种情况时以下两种写法是完全不同的

\\(query(l1,l2,1).rmax+query(l2,r2,1).lmax-a\[l2\]\\)

\\(query(l1,l2,1).rmax+query(l2+1,r2,1).lmax\\)

第二种写法是错误的，这是因为\[l2,r2\]中次大的的子段和可能不包含l2，这个时候query(l2+1,r1,1).lmax就不能得到正确的答案了。

### [【模板】普通平衡树][Link 1] ###

本题使用Treap解决。

其实处理本题普通的BST就可以胜任，但是对于特殊数据（比如链）则会退化到O(n)。

平衡树就是为了防止这一类特殊数据影响复杂度而诞生的，因而名为“平衡”。

Treap，顾名思义，就是Tree+Heap。

它在普通BST的基础上，赋予每个节点一个额外的值，在维护过程中如果这个值不满足小根堆的性质则进行旋转，从而使树的结构更加平衡。

为了确保在任何情况下都不会被数据卡，这个额外值采用随机赋值。

这样Treap就可以保证平衡，也就不会退化到线性时间复杂度了。

### [线段树][Link 2] ###

维护两个标记，但是需要考虑先后顺序。

如果先加法，那么需要除法操作，涉及到精度问题，不可取。

所以先乘法。

转载于:https://www.cnblogs.com/ilverene/p/11181345.html

[Can you answer these queries I]: https://www.luogu.org/problemnew/show/SP1043
[Can you answer these queries III]: https://www.luogu.org/problemnew/show/SP1716
[Can you answer these queries IV]: https://www.luogu.org/problemnew/show/SP2713
[Can you answer these queries V]: https://www.luogu.org/problemnew/show/SP2916?tdsourcetag=s_pcqq_aiomsg
[Link 1]: https://www.luogu.org/problemnew/show/P3369
[Link 2]: https://www.luogu.org/problemnew/show/P3373