A - Description
给定字符串 \(S\) 和 \(T\)，问你在 \(S\) 中 \(T\) 出现了几次。
\(1\le |S|,|T|\le 2\times 10^6\)
A - Solution
首先暴力地来想。在 \(S\) 中找出所有长度为 \(|T|\) 的子串，然后暴力逐字符匹配，复杂度显然是 \(O(n^2)\) 的，考虑优化。（此处假设 \(|T|\) 与 \(|S|\) 同阶，记为 \(n\) ）
枚举所有子串的过程较难优化，我们考虑优化逐字符匹配的过程。逐字符匹配本质上就是比较两个字符串是否相等，那我们能否将这个过程优化成 \(O(1)\) 呢？
于是，字符串哈希应运而生。我们可以使用字符串哈希将字符串压成一个数，然后就可以 \(O(1)\) 比较了。考虑将这个字符串转化为一个 \(k\) 进制数，也就是给第 \(i\) 位乘上 \(k^{i-1}\) 的权值。防止大数溢出，可以设定模数进行取模（不过大多数时候 unsigned long long 是不错的选择）
时间复杂度 \(O(n)\)，瓶颈在于枚举长度为 \(|T|\) 的子串。
B - Description
给定字符串 \(S\)，有 \(q\) 次询问，每次询问给出 \(x\) 和 \(y\)，让你求字符串 \(s_1=S_xS_{x+1}\cdots S_{n}\) 和 \(s_2=S_yS_{y+1}\cdots S_n\) 的最长公共前缀长度。
B - Solution
还是暴力地来想。假设答案为 \(len\)，那么就有 \(S_xS_{x+1}\cdots S_{x+len-1}=S_yS_{y+1}S_{y+len-1}\) ，有了前面的哈希支持，我们可以做到 \(O(1)\) 判断这个式子。我们现在可以枚举从 \(1\) 到 \(n-\max(x,y)+1\) 的每个 \(len\)（记 \(n=|S|\)，下文如没有特殊说明均代表此含义），时间复杂度是 \(O(qn)\) 的。
进行一些观察，我们发现 \(len\) 是具有单调性的。具体来说，如果 \(len=5\) 时满足条件，那么 \(n=4\) 时一定满足，因为这是被 \(len=5\) 完全包含的。如果令 \(a_i\) 代表 \(len=i\) 时是否符合条件，那么 \(01\) 数组 \(a\) 的形式一定是 \(1111\cdots 10000\cdots 0\)。
因此，我们考虑二分 \(len\)。具体地，每二分出一个 \(mid\)，我们使用哈希 \(O(1)\) 判断是否符合条件，如果符合就去二分 \(>mid\) 的值，如果不符合就二分 \(<mid\) 的值。时间复杂度为 \(O(q\log n)\)，可以通过。
C - Description
给你一个由小写英文字母构成的字符串 \(S\)，求 \(S\) 中最长回文串的长度。
\(1\le n\le 10^6\)。
C - Solution
我们先从回文串的定义角度入手。通俗一点来说，回文串就是指从前往后读和从后往前读是相同的。形式化地，对于一个字符串 \(s\)，有 \(s_1s_2\cdots s_n=s_ns_{n-1}\cdots s_1\)。不过貌似和最长没有什么关系，所以换一种方法表示。\(s_1s_2\cdots s_{mid}=s_{n}s_{n-1}\cdots s_{mid}\)。现在我们把答案扩展到了一个 \(mid\) 上。\(mid\) 是可以从 \(1\) 到 \(n\) 枚举的，所以现在只需要考虑 \(mid\) 为定值时的情况。
对于这种极值问题，我们可以将它转化为判定性问题。具体地，对于每一个 \(1\le mid \le n\)，我们需要求出最大的 \(len\)，使得
根据上一道题的观察，\(len\) 也是具有单调性，可以二分的。而上面的式子也是可以哈希 \(O(1)\) 判断的。因此，我们解决了这个问题。
流程如下：
- 枚举每个 \(1\le mid \le n\)，需要 \(O(n)\)
- 二分出最大的 \(len\)，满足上面的等式（哈希判断），需要 \(O(\log n)\)。
哦哦其实并没有解决这个问题。因为我们还不知道如何求解一个区间内字符的哈希值。
我们先列出来最基本的求区间 \(\left [ 1,i\right ]\) 哈希的式子：
那么如何用已知的 \(hash\) 数组表示一个区间 \(\left [ l,r\right ]\) 的哈希值？
写点解析吧。
第一行：将 \(l\) 到 \(r\) 这个子串表示为 \(base\) 进制数。可以理解为把 \(l\) 到 \(r\) 单独看成一个字符串重新哈希得到的值。
第二行：类似前缀和的操作，显然正确。
第三行：注意到这个式子中减号前后的形式基本与最开始的哈希式子一样，于是改写成 \(hash\) 数组。后者在区间哈希的式子中 \(base\) 的幂次是 \(r-j\)，而写成 \(hash[l-1]\) 的话幂次就应该是 \(l-1-j\)。
第四行是简单化简，于是我们得到了 \(O(1)\) 区间哈希的方法。
综上，时间复杂度为 \(O(n\log n)\)。
D - Description
给你一个长度为 \(n\) 的序列 \(a\)，保证对于每个 \(1\le i\le n\) 有 \(1\le a_i\le n\)，有 \(q\) 次询问，每次询问给定两个正整数 \(l,r\)，你需要回答区间 \(\left [l,r\right ]\) 是否是 \(\left [1,r-l+1\right ]\) 的排列。
\(1\le n,q\le 10^6\)。
D - Solution
首先，我们发现如果 \(\left [ l,r \right ]\) 是 \(\left [ 1,r-l+1 \right ]\) 的排列，那么这两个区间和一定相等。因此， \(\left [l,r \right ]\) 的区间和一定等于 \(\frac{x\times (x+1)}{2}\)（\(x=r-l+1\)，即为区间长度）。只有这一个条件显然是不严谨的，我们再将排列的基本性质放到限制里：区间中的 \(x\) 个元素各不相同。
形式化地，满足下面两个条件的区间是符合条件的。
- \(\forall \ l\le i,j\le r\)，如果 $i\ne j $ 有 \(a_i\ne a_j\)。
- \(sum(l,r)=\frac{x\times (x+1)}{2}\)
第二个条件显然是可以 \(O(1)\) 判断的，所以我们只需考虑第一个条件。
如何用更方便观察的方式记录区间内是否有相同元素？我们考虑记 \(pre_i=j\) 来代表 \(i\) 左侧第一个等于 \(a_i\) 的数下标为 \(j\)（如果不存在 \(j\) 则即 \(pre_i\) 为 \(0\)）。于是我们有了新的条件。
- \(\forall\ l\le i\le r\)，有 \(pre_i<l\)。
\(O(n)\) 预处理 \(pre\) 数组，暴力判断每个 \(pre_i\)，我们成功做到了 \(O(nq)\) 的复杂度。
我们较为巧妙地想到将 \(l\) 到 \(r\) 的区间判定性问题转化到整个序列。显而易见地，对于所有 \(1\le i<l\)，都有 \(pre_i<l\)，这是一个事实，是百分之百存在的。我们可以从二进制角度看，把这个事件的值记作 \(1\)。
而上面 \(l\) 到 \(r\) 的这个条件是有待判断的，不是百分之百存在的。我们记作 \(0\)。
注意到 \(1\& 0=0\)，也就是说全局来看，我们对于 \(\left [ l,r\right ]\) 的约束和我们对于 \(\left [1,r \right ]\) 的约束是等价的，是不影响结果的。
于是，我们又有了新的条件。
- \(\forall \ 1\le i\le r\)，都有 \(pre_i<l\)。
这次就好搞了。我们预处理出 \(pre\)，然后做一个类似前缀和的东西维护 \(\left [1,r \right ]\) 中 \(pre\) 的最大值，询问时就可以做到 \(O(1)\) 判断。
最终，我们成功地做到了 \(O(q)\) 的复杂度。
)
)
)
