瞎扯最大子矩阵

摘要

本文所研究的是一类序列上的“最大子矩阵”问题(其实就是瞎扯)。

序列最大子矩阵

给出一个非负整数序列 ,并定义

则最大化 则被称为是该序列的一个最大子矩阵。

sample

单调栈

这个问题可以使用单调栈解决。维护一个元素单调递增的栈,每次插入元素,在弹栈的时侯更新答案。插入完之后,一个一个把栈弹空并更新答案。具体的算法过程自行左转。

时间复杂度

笛卡尔树

具体见博客-笛卡尔树

时间复杂度

带修改序列最大子矩阵

具体的问题见我出的题目最大子蒟阵。简化题意就是支持区间覆盖,区间翻转,求全局最大子矩阵。操作中涉及的权值以及初始时的权值是随机的。

基于不带修改的问题的笛卡尔树做法,想到使用 Treap 解决(Treap 是笛卡尔树)。每个结点维护子树所代表区间的最大子矩阵的面积。显然这个信息是可以向上合并的。因此再使用一些普通的平衡树操作以支持区间翻转和区间覆盖即可。

时间复杂度

环上最大子矩阵

将数排成一个环,求最大子矩阵。

这道题容易让人想偏,但它实际上是一个脑筋急转弯。

考虑环上的一个最小权值 。如果最优方案包含 ,那么显然我们会贪心地选择整个环的所有结点,答案为 ;否则最优方案不包括 ,那我们就把这个元素删掉,断掉环,然后做一次序列最大子矩阵即可。

时间复杂度

树上最大子矩阵链

将上述问题拓展到树上,相当于我们选择一条路径,最大化路径上元素的“面积值”。

有关树上路径的问题,容易想到点分治。

对于从分治重心挂下来的链,我们可以DFS,在DFS时用单调栈维护到重心路径上的最小点权。这样就可以计算这部分的值,更新答案。

对于经过分治重心的链,考虑记录 表示高度为 的矩形,从分治重心挂下来的路径长度最长为 。对于属于不同的根子树的两个 ,显然可以用 更新答案。于是我们需要维护一个结构,支持

  1. 与结构中的二元组更新答案;
  2. 插入一个二元组

仍然可以使用 Treap 维护(前提是权值随机,则复杂度 )。

树上最大子矩阵块

我们还可以拓展为,找一个连通块,使得块内的元素的面积值最大。

这个问题可以使用并查集解决。我们将点权转化为边权(取端点的min),然后将边按边权排序,从小到大加边,然后维护连通块大小以更新答案即可。

复杂度


  转载请注明: Sshwy's Blog 瞎扯最大子矩阵

 上一篇
一套题与心路 一套题与心路
摘要 感觉是精神状态不大好的原因吧 A 给定一个 01 序列,请你找到一个最长的子序列,使得第一个 1 到开头的距离、相邻两个 1 之间的距离、最后一个 1 到结尾的距离都相同。例如00100100和0001000就是符合要求的子序列,0
2019.09.15 Sshwy
下一篇 
小志 小志
摘要 谨以此文,在我疲倦、颓废、迷茫的时侯,给我指引方向。 2019.8.30恩师的寄语 尧尧妈妈,第一,尧尧是我寄予大期望的孩子,必须也应该在以后考上非常好的大学,找到最好的工作,成就很大的事业。第二,关于信竞的事,首先与徐老取得联系
2019.08.16 Sshwy
  目录