前置：
1. 目前没有进行代码实现，所有内容均是口胡，如有错误或者不严谨的地方烦请指出，谢谢！
2. 由于这篇文章中会同时出现 “线段树上的节点”，“树上的结点” 等多种点，为便于理解，维护连续段的线段树的点统称 “节点”，树的点统称 “结点”。
3. 线段树上的节点对应/表示的区间指线段树函数参数中的 $l$，$r$。
书接上回，上一次通过利用离线的性质有了一个 $O(len\,\log n\,\log len\,+\,q\,\log n)$ 的做法，回忆一下是怎么做的：
1. 通过 SAM 将这道题转化为数据结构题：一棵树，叶子节点有颜色，点有点权，保证任何一个点的权值大于父亲节点的权值，每次询问子树内包含 $[l,r]$ 所有颜色的所有节点中权值的最大值。
2. 想到可以按照节点权值大小合并儿子，维护颜色连续段，当产生新的连续段时查询有没有可回答的询问。
之所以用了两个 $\log$，瓶颈在于维护连续段用的是 set + 启发式合并。
想一想，有没有什么数据结构可以 1 个 $\log$ 的维护相关信息？
不如试试线段树合并？( 这里是受到了 NOI2018 你的名字 的启发 )
如果可以做到刚好在产生新的连续段时去查找有没有新的可回答询问，理论上是可以实现 1 个 $\log$ 的 (查询可回答询问的部分可以看这题洛谷题解中用户 “xtx1092515503” 的文章 ，讲的比较清晰，我在上一篇博客中口胡的那个有问题)。
这里又有一个经典处理方式，受 【美团杯 2020】半前缀计数 启发，我们可以考虑把每个连续段在它的” 最后出现时刻” 计算 ( 这里的” 最后出现时刻” 比较抽象，也许看到最后会帮助理解 )，具体到这道题中，我们考虑：
对于一个连续段，我们令 “线段树上能覆盖整个连续段的深度最大的节点” 为 $x$，那么有如下性质：
1. 这个连续段跨过 $x$ 对应区间的正中间 ( 否则 $x$ 的左 / 右儿子能覆盖整个连续段 )。
2. 对于树上一个结点，子树内的所有连续段，对应的 $x$ 各不相同 ( 由 1 可得 )。
定义 $x$ 和这个连续段 “对应”。
相当于构造了一个线段树上节点和连续段的双射。
所以，如果我们能对于一个节点的维护连续段的线段树的所有节点，维护跨过其中点的连续段的最左端和最右端，就可以知道所有连续段的信息。
这个信息可以很简单的通过 push_up 来维护。只要记 $f(id,0/1)$ 表示线段树节点 $id$ 表示区间的最长前缀连续段和最长后缀连续段。
考虑三种情况：
1. 一个连续段在其对应的线段树节点表示的区间中既不是前缀也不是后缀，这种情况直接在线段树合并遍历到这个节点时查询一下跨过其中点的连续段的最左端和最右端，如果和合并之前的两个线段树都不相同 ( 说明产生了新的连续段 )，就去查询有无新的可回答询问。
2. 一个连续段在其对应的线段树节点表示的区间中是前缀或后缀，假设是前缀，后缀同理。这时如果直接对每个跨越中点前缀询问复杂度会多出一个 $\log$。这时考虑到，这个连续段的存在一定会导致在其对应线段树节点某个祖先 ( 其实就是最近的是其父亲节点的右儿子的祖先 ) 的左儿子的后缀最长连续段长度是 0( 否则违背假设 )，右儿子前缀最长连续段就是这个连续段。实现的时候在这个节点进行情况 1 的考虑即可。或者在之前定义对应时就把这个连续段的对应线段树节点修改为这里提到的这个 “祖先” 也行，仍然是满足双射的。
3. 既是前缀也是后缀，显然这个节点表示的区间的颜色在当前子树内都存在，这时可以直接对这样的线段树节点表示区间进行询问，总询问次数不超过线段树总结点个数，也就是 $2n$ 的。
复杂度分析：
线段树合并的部分：parent 树上每一个叶子节点上插入一种颜色，总插入次数不超过 $O(len)$。合并复杂度不超过 $O(len \, \log n)$。在合并到某个节点时同时处理连续段的变化 (在每个节点上操作次数不会超过常数次)，不影响复杂度。
广义 SAM：$O(\lvert \Sigma \lvert \, len)$。
查询询问： $O(q\,\log n \, + \, len\, \log n)$。
总复杂度：$O(\lvert \Sigma \lvert \, len\,+\,q\,\log n \, + \, len\, \log n)$。
0 条评论