Luogu4482 [BJWC2018] Border 的四种求法

题意：给出字符串 ， 次询问子串 的最长 Border 长度。

，时限 。

---

记 为前缀 的最长公共后缀长度。

则求 的 Border 相当于找到一个 中最大的 满足 。

这个 正是两个前缀节点 Parent Tree 上 LCA 的 值。

这看起来很不好直接使用数据结构维护，可能需要树链分治。

先考虑暴力跳 Parent Tree 的做法。即枚举前缀 在 Parent Tree 上的所有祖先 ，令 ，再考虑有那些 。维护 的 endpos 集合 ，则最好的 是 中在 内的最大元素。

这可以线段树合并维护 endpos，然后区间查询。

---

为了不那么暴力，将树树剖，一个询问就会被拆成对 条重链的询问。

假设从点 进入该重链，则从上到 的路径，LCA 为上方的重链点， 向下的路径，LCA 为 本身。

注意,这可能会产生上下重复的路径，但是容易发现答案更劣，所以不用除去。

对于一条重链，我们需要解决如下的子问题：

记 为 SAM 的前缀节点 与当前重链的 LCA 的 。

将重链的节点从浅往深编号为 ，记 为第 个节点的 endpos 集合，它是递减的。

每次对一个前缀 ，询问 对一个后缀 ，询问

需要考虑的“前缀节点”的数目是每条轻链头的子树大小和，为 。可以对每条重链分别暴力计算 ，并分别处理这个类似偏序的问题。

第一维 不难解决，使用区间数据结构：线段树。

对于第二维 或 ，可以在线段树上记下 或 的区间最小值，即可判断某个区间内是否可能有解。

然后使用线段树上二分即可。

写起来大概就是先把询问挂到重链上，然后对每条重链，暴力 DFS 轻子树。

然后离线处理，对每条重链前后扫描线两次，将轻子树依次从上到下加入线段树（不必动态开点），就能得到每个前缀/后缀的状态。

这样空间复杂度就是 ，时间复杂度为 ，常数不大。