Loj#6041 「雅礼集训 2017 Day7」事情的相似度

题意：给出一个 串 。

每次询问给出 ，要求取 且 ，使得前缀 的最长公共后缀最大。回答这个最大值。

，时限 。

---

两个前缀的最长公共后缀，即为其在 SAM 的 Parent Tree 上 LCA 的 值。

于是，本题可以转化为树上数据结构问题：

给出一棵 个节点的树，节点标号为 。

每次询问给出 ，求

序列扫描线。离线按 增大的顺序回答询问。当 增大 时，会加入对子 。

类似单调队列，对于对子 ，若 且 ，那么对子 就是没用的。

这引出一个算法：枚举 的祖先 （即枚举 LCA），记集合 ，则 中的点和 的 LCA 都是 （或更深）。

根据上述规则，只有 中最大的元素可能是最优解。

记 。每次加入点 ，将这个点到根的路径覆盖为 ，得到的就是 。

枚举 的祖先时， 形成若干个连续段，只有每个连续段的最深点可能是最优解。

维护 为询问 的答案。对于每个段，会对 产生一次区间取 。

枚举 的连续段、覆盖 的过程就是 LCT 的 access。用 LCT 维护，会产生 次连续段变动（对应 的修改），总复杂度 。