0x40 数据结构进阶

桃扇骨 2021-10-19 03:31 276阅读 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就不能得到正确的答案了。

【模板】普通平衡树

本题使用Treap解决。

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

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

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

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

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

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

线段树

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

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

所以先乘法。

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

发表评论

表情：
评论列表 （有 0 条评论，276人围观）

还没有评论，来说两句吧...

相关阅读