题解：P10611 故事结局

chenxinyang2006 · 2024-06-16 23:28:13 · 题解

• 对时间轴分治

  对修改操作颜色段均摊，那么可以知道一个颜色段存在的时间会是时间轴上的一段区间。

  对事件轴线段树分治，就转化为了所有修改在所有查询前面的子问题，所有子问题规模和是 O(q \log q) 的，这个子问题实现得好可以 1log，实现不好 2log 卡一卡常（或者大力乱搞一下，考虑这题是 RMQ 有一些经典乱搞比如 log 分块）估计也能过。

  不是正解，但是卡不掉！强制在线一下就寄了，但正解由于空间问题不能在线。

• 正解

  我们假装还是要强制在线的，所以不考虑上面的离线做法。

  首先你发现如果操作是行向 v chkmax，应该挺好做的：建立树套树，行为外层，列为内层。外层树上每个节点相当于维护了一个长度为 m 的序列，每个位置代表这个节点对应的行区间上，所有这一列的值的 \max。于是以修改查询都多 1log 的代价降一维，一维（序列）的情况当然是好做的。

  现在变成对一行的一个区间 assign 了，还是像刚才一样建立树套树，外层树上每个节点维护一个长度为 m 的序列，是这些行逐列叠 \max 的结果。

  从 chkmax 变为 assign 的问题在于现在你可能需要 pushup 了，这当然是没法接受的，至少不能对于整棵树 pushup。

  考虑刚才的一维情况，其实维护的是支持区间 chkmax，区间 max 的线段树，每个节点上维护的两个信息分别是这个节点上的 chkmax 标记和这个节点子树内所有 chkmax 标记作用出的子树最大值。一个好处是，外层树上的点 u，它对应线段树上每个点的信息可以是其外层树上左右儿子线段树上每个点信息的叠加（标记和子树最大值均直接取 \max），这具有相当的一致性，使得我们有可能进行 pushup。

  考虑先对外层树上的叶子节点（也就是只维护一行信息的节点）进行修改然后一路 pushup 上去，我们把区间 assign 操作强行转化为区间 chkmax 操作：用 chkmax 标记代替 assign 标记，首先没递归到完全包含的点时标记正常下传，递归到完全包含的点时试图给这个点打上标记，并取消子树内所有点已有的标记。设势能为线段树上有标记的节点数量就可以发现总复杂度不超过 O(q \log m)，这里指的是只考虑所有外层树上叶子节点的复杂度开销。

  这样对外层树上最底层的点的线段树可以进行修改，因为外层树上所有非叶节点的线段树信息都只是其左右儿子信息的简单叠加，所以向上 pushup 的时候只需要 pushup 最底层修改时修改到的节点，可以发现时间复杂度不超过 O(q \log n \log m)。

  然后你发现在线实现这个算法需要 2log 空间，肯定 MLE 了。可以考虑离线对外层树逐层处理（从低往高一层一层处理，每次只存相邻两层每个节点对应线段树可持久化后的结果）可以 1log 空间。

  时间复杂度 O(n+m + q \log n \log m) 空间复杂度 O(m+q \log m)。

• 一些拓展

  实际上也不是一定卡不掉离线做法，直接强制在线，然后用 压缩 Trie 可能可以在线降到 1log 空间，但压缩 Trie 一般是处理单点修改的，这题需要区间修改并且对线段树结构的依赖性比较大（比如你拿平衡树维护区间 chkmax 区间 max 显然就不能 pushup 了），这具体能不能做到还需要进一步研究。

  但是如果真用到压缩 Trie 了这题还能写吗。

  另一方面，其实也可以明确一下这个做法能支持在怎样的代数结构上运算。考虑一个代数系统 G=<A,+,\cdot>，<A,+> 构成交换半群（交换律，结合律），<A,\cdot> 构成半群（结合律），\cdot 对 + 有分配律，那么事实上将本题的求和换成这个代数系统中的 +，A_{i,j} 与 b_j 相乘换成这个代数系统的 \cdot，做法也是可以沿用的。

  事实上即使允许离线，所有修改在查询前的子问题如果只保证 <A,+> 只有交换律结合律也不能直接 1log 做，应该会多一个 \alpha，复杂度会略差一点。不过本题的 + 操作实际上是取 \max 而 RMQ 确实是可以 O(n)-O(1) 的。

  如果 + 直接是整数加法，\cdot 直接是整数乘法的话相当于 <A,+> 变为交换群（所有元素有逆元），这是一个比较常见的情况，这题相当于探讨了 + 不可求逆的情况。