题面描述

小C对字符串颇有研究，他觉得传统的字符串匹配太无聊了，于是他想到了这样一个问题．

对于两个长度为 \(n\) 的串 \(A, B\) , 小C每次会给出给出 \(4\) 个参数 \(s, t, l, r\) . 令 \(A\) 从 \(s\) 到 \(t\) 的子串(从 \(1\) 开始标号)为 \(T\)，令 \(B\) 从 \(l\) 到 \(r\) 的子串为 \(P\).然后他会进行下面的操作：

如果 \(T\) 的某个子串与 \(P\) 相同，我们就可以覆盖 \(T\) 的这个子串，并获得 \(K - i\) 的收益，其中 \(i\) 是初始时 \(A\) 中(注意不是 \(T\) 中)这个子串的起始位置，\(K\)是给定的参数．一个位置不能被覆盖多次．覆盖操作可以进行任意多次，你需要输出获得收益的最大值．

注意每次询问都是独立的，即进行一次询问后，覆盖的位置会复原．

对于所有数据，有 \(1 \le n, q \le 10^5\) ，\(A, B\) 仅由小写英文字母组成，\(1 \le s \le t \le n, 1 \le l \le r \le n, n < K \le 10^9\)．

对于 \(n = 10^5\) 的测试点，满足 \(51 \le r - l \le 2000\) 的询问不超过 \(11000\) 个，且 \(r - l\) 在该区间内均匀随机．

题解

考试时看到这道题名称是Cover，就决定写这篇题解。。。。

其实是很烦的一道题，，全靠那个神仙的条件保证复杂度。。。

因为“\(51 \le r - l \le 2000\) 的询问不超过 \(11000\) 个”，而对于每个询问，对答案有贡献的串不超过\(n/(r-l+1)\)个，算一算发现这\(11000\)个询问总共不会访问到40w个串。。。也就是说，每次线段树暴力找后继就可以了。。。。

对于\(r-l<51\)的情况，显然串的总数不超过\(50n\)。离线，相同长度的串一起处理，用Hash快速求出和当前位置的串相同的最近的下一位置。然后倍增一下就好啦。

代码

太丑了，不放了。