告示牌识别：题解¶

解法比较¶

出题人实现从后往前插入后缀，用 Treap 按“首字符、下一后缀的顺序标签”排序；这是后缀字典序的递归定义。旋转后重标相应子树，标签取浮点区间中点。得到后缀数组和相邻 LCP 后，对每次询问、每个来源分别向左右扫描，求与其他来源的最长公共前缀，再扣掉不能独占的长度，计数依据与下文一致。

标签必须始终严格有序；固定精度中点可能重合，属于需要修复的数值实现问题。出题人实现在一次插入的旋转完成后，还可能重标整棵子树，构造的保守最坏界为 \(O(S^2)\) ，询问扫描为 \(O(qnS)\) ，空间为 \(O(S)\) .Codex（GPT-6）采用的实现使用整数排名的比较排序倍增，构造为 \(O(S\log^2(S+1))\) ；各来源的共有长度只预处理一次，扫描与询问共 \(O((n+q)S)\) ，空间仍为 \(O(S)\) .收益是精确排名、明确的构造界及避免逐询问重复来源扫描；后缀数组与 LCP 计数本身来自出题人解法。

对每个起点找最长公共前缀¶

固定字符串 \(s_i\) 中的一个起点 \(x\) .令 \(h_x\) 为这个后缀与其他字符串任意后缀的最长公共前缀长度的最大值。如果没有其他字符串，取零。令 \(r_x\) 为从 \(x\) 到本串结尾的字符数。

长度不超过 \(h_x\) 的前缀还出现在其他串中；长度大于 \(h_x\) 的前缀均不在其他串中。因此一次询问的贡献为

\[ \max\bigl(0,\min(R,r_x)-\max(L,h_x+1)+1\bigr) \]

对所有起点求和即可。这里没有去除同一字符串中的重复内容，因为题目要求按出现位置计数。

后缀数组与相邻 LCP¶

把所有字符串用互不相同、且不属于小写字母的分隔符连接。记录每个位置所属字符串和 \(r_x\) ；分隔符位置的 \(r_x=0\) .独特分隔符保证不同后缀的公共前缀不会越过原字符串的边界。

参考实现用倍增构造后缀数组 Suffix ：先按首字符，再按两个长度为 \(w\) 的排名块排序，将 \(w\) 翻倍，直到所有后缀排名互不相同。使用整数排名和比较排序，避免浮点标签。

随后用线性扫描的 LCP 算法求相邻后缀的公共前缀长度。定义 \(LCP[j]\) 为排序中第 \(j-1\) 与第 \(j\) 个后缀的 LCP。任意两个后缀的 LCP 等于它们之间相邻 LCP 的最小值：这些后缀夹在相同字典序前缀区间内，区间最小值决定能共同保留多少字符。

只找左右最近的其他来源¶

对某个来源 \(i\) ，从左到右扫描后缀数组。遇到前一个后缀不属于 \(i\) 时，从当前相邻 LCP 重新开始；否则持续取最小值。这样得到每个属于 \(i\) 的后缀与左侧最近的其他来源后缀的 LCP。反向再扫描一次，得到右侧结果，两者取最大值。

为什么不用比较更远的后缀？到更远后缀的区间包含到最近后缀的区间，最小值只可能更小，不可能更大。因此左右最近候选已经给出 \(h_x\) .分隔符可以当作其他来源处理，其与字母开头的后缀 LCP 为零，不会制造错误的公共子串。

正确性与复杂度¶

左右扫描求出了每个起点与其他字符串的最长共有长度；贡献公式恰好保留所有超过此长度、又没有越过本串结尾的询问长度。每个起点和长度唯一确定一次出现，故求和既不遗漏也不重复计数。

令 \(S\) 为所有字符串长度之和加分隔符数量。比较排序版倍增的时间为 \(O(S\log^2(S+1))\) ；LCP 为 \(O(S)\) ；来源扫描与询问共 \(O((n+q)S)\) .空间为 \(O(S)\) .答案及询问端点使用 64 位整数，即使询问长度远大于字符串，也直接按公式截断。

独立对拍直接枚举所有位置区间，用字符串集合记录出现过的来源，再逐次计数；包括完全相同串、单串、重复字符和很大的询问端点。

程序与复现¶

参考程序见 std.cpp。使用 C++17 编译后，可用 tests/generate.py --out-dir <题目目录以外的路径> --std <程序路径> 生成输入和答案。固定种子与用例目的见生成计划。性能测量见评测环境与性能。