题目描述

给定两个长度为 (n) 的字符串 (A, B)，每次询问给出 (s, t, l, r)，令
(T = A[s..t]), (P = B[l..r])。

可以在 (T) 中选择若干个与 (P) 相等的不重叠子串进行覆盖，每个子串若在原串 (A) 中起始位置为 (i)，则获得收益 (K-i)。
询问独立，求最大收益。

问题转化

对于每个询问，我们需要：

1. 找到 (P) 在 (A) 中的所有出现位置（起始位置）集合 (L)。
2. 只保留 (L) 中在区间 ([s, t-|P|+1]) 内的位置。
3. 从中选择一些位置，使得任意两个被选位置之差 (\ge |P|)（保证不重叠）。
4. 最大化总收益 (\sum_{i \in \text{选择集合}} (K-i))。

核心算法步骤

1. 快速找到匹配位置（字符串匹配部分）

• 对 (A) 建立后缀自动机（SAM），在每个状态节点上记录原串中出现该子串的所有结束位置 endpos（由于内存限制，通常记录最小的若干个或通过线段树合并存储全部 endpos）。
• 对于询问的 (P = B[l..r])，在 SAM 上跑匹配：
  从初始状态开始，按 (B) 的字符走，直到走完 (P)。
  如果走完长度 (= |P|)，则当前节点对应的所有 endpos 位置 (e)，对应的起始位置 (i = e - |P| + 1) 就是 (P) 在 (A) 中的所有出现起始位置。
• 利用线段树合并预处理 SAM 每个节点的 endpos 集合，这样我们可以快速得到某个节点中位于 ([s+|P|-1, t]) 范围内的 endpos，从而得到起始位置在 ([s, t-|P|+1]) 内的匹配。

2. 选择不重叠位置以最大化收益（DP 部分）

设得到的合法起始位置集合为 (L = {i_1, i_2, \dots, i_m})（已排序）。
我们做 DP：
定义 (dp[j]) 表示考虑前 (j) 个位置，且选择了第 (j) 个位置时的最大收益。
转移：
[ dp[j] = (K - i_j) + \max{0, \max_{k: i_j - i_k \ge |P|} dp[k]} ] 边界：若前面没有满足条件的位置，则只选自己，收益为 (K - i_j)。

由于 (i) 递增，对于每个 (j)，找到最大的 (k) 满足 (i_j - i_k \ge |P|)（即 (i_k \le i_j - |P|)），这可以通过在 (L) 上二分得到。
然后求前缀 (dp[1..k]) 的最大值，可用前缀最大值数组维护，做到 (O(m \log m)) 处理一次询问的选择。

3. 复杂度优化依据数据特点

数据范围提示：对于长度在 ([51,2000]) 的 (P)，询问较少（≤11000 个）。

• 当 (|P|) 很长时，匹配位置 (m) 很小（长串重复出现少），直接做上述 DP 即可。
• 当 (|P|) 很短（≤50）时，匹配位置可能很多，但此时由于长度短，相邻可选位置间隔小，可以通过贪心选择最靠前的位置（因为收益 (K-i) 随 (i) 增大而减小），选择策略是：从左到右扫描，能选就选，选了之后跳过 (|P|) 的长度。这样可以在 (O(m)) 时间解决。
• 当 (|P|) 很大时，匹配少，DP 快。

这样总复杂度可以控制在 (O(n \log n + q \log n + \sum m \log m)) 且 (\sum m) 在数据下不会太大。

算法流程

1. 读入 (A, B)，对 (A) 建 SAM，并预处理每个状态的 endpos 集合（线段树合并）。
2. 对于每个询问：
   • 在 SAM 上匹配 (P = B[l..r])，得到对应状态节点。
   • 查询该节点 endpos 中在区间 ([s+|P|-1, t]) 内的位置，得到起始位置集合 (L)（转换为起始位置）。
   • 对 (L) 排序，用上述 DP（或贪心）计算最大收益。
3. 输出每个询问的答案。

时间复杂度

• SAM 构建：(O(n))。
• 线段树合并预处理 endpos：(O(n \log n))。
• 每个询问匹配：(O(|P| + \log n)) 找到节点。
• 每个询问选择计算：(O(m \log m))，(m) 为匹配位置数。
  在数据特点下总复杂度可接受。

样例验证

以第一个询问为例：

n=10, K=11
A = abcbababab
B = ababcbabab
询问: 1 9 7 9
T = A[1..9] = abcbababa
P = B[7..9] = aba
匹配起始位置（全局）：i=1, 5, 7, ...
在区间 [1, 9-3+1=7] 内：i=1, 5, 7
选择不重叠（差≥3）：
选 i=5：收益 11-5=6
其他重叠：i=1 与 i=5 差4≥3 可选，但 i=1 收益=10，i=5 收益=6，总=16？  
检查：i=1 时覆盖 [1,3]，i=5 时覆盖 [5,7]，不重叠，总收益=10+6=16？但样例输出是6。  
说明样例中只选了 i=5，为什么？
因为 i=1 时覆盖 [1,3] 在 T 中（即 A[1..9]）但 A[1]=a, A[3]=c，子串 A[1..3]=abc≠aba，所以 i=1 不是有效匹配？  
核对：A[1..3]=abc 对，所以 aba 在 A 中确实出现在 i=5, i=7, ...，所以 i=1 不在匹配集中。  
所以只有 i=5 可选（i=7 与 i=5 重叠）。  
收益 = 11-5=6，符合输出。

核心难点

• 快速得到 (P) 在 (A) 中某个区间内的所有匹配起始位置（字符串匹配数据结构）。
• 在匹配位置集合上做带距离约束的最大收益选择（DP+二分）。
• 根据 (|P|) 长度不同采用不同策略以保证效率。