自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:07:18，当前版本为作者最后更新于2022-11-05 08:09:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P5115 Check, Check, Check one two!

看到题目，我首先想到建出正反串 SA 及其 $ht$ 的笛卡尔树，并在一棵树上启发式合并，另一棵树上用 P4211 LCA 套路做，掐指一算发现时间复杂度是 $\mathcal{O}(n\log ^ 3 n)$，虽然离线（枚举 LCA，考虑较小子树对较大子树的贡献，将询问离线扫描线）后三个 $\log$ 分别是启发式合并，BIT 和树剖，显然卡不满，但是依然非常难写。

稍微观察一下 $\mathrm{lcp}(i, j)$ 和 $\mathrm{lcs}(i, j)$，它们拼接起来形成长为 $\mathrm{lcp}(i, j) + \mathrm{lcs}(i, j) - 1$ 的相等子串，联想到优秀的拆分，这启发我们在 $(i - \mathrm{lcs}(i, j) + 1, j - \mathrm{lcs}(i, j) + 1)$ 处统计贡献。因为相等子串的要求 极长，否则 $\mathrm{lcp}(i, j)$ 或 $\mathrm{lcs}(i, j)$ 可以更大，所以枚举 $i, j$，若 $s_{i - 1} \neq s_{j - 1}$，则 $s[i, i + \mathrm{lcp}(i, j) - 1]$ 产生贡献。进一步地，我们发现贡献和 $i, j$ 具体无关，仅和 $L = \mathrm{lcp}(i, j)$ 相关，为 $f(L) = \sum\limits_{p = 1} ^ L p(L - p + 1) [p\leq k_1][L - p + 1 \leq k_2]$。$f$ 可以 $\mathcal{O}(n)$ 预处理。

对于 $s_{i - 1} \neq s_{j - 1}$ 的要求，直接容斥。问题转化为求与任意两个 $(i, j)(i < j)$ 的 $\mathrm{lcp}(i, j)$ 相关的式子。经典套路，直接对 $ht$ 做扫描单调栈，对于当前 $i$ 实时维护 $\sum\limits_{1\leq j < i} f(\min_{p = j + 1} ^ i ht_p)$ 即可。时间复杂度 $\mathcal{O}(n(\log n + |\Sigma|))$。

理论可以做到关于长度加字符集线性（线性 SA，线性区间 RMQ），但不实用。

听说官方题解是 $\log ^ 2 n$ 的边分树，应该是对题解一开始的 $\log ^ 3 n$ 思路应用更多套路。对比两种做法，直接硬做没有用到拼接成相等子串的性质，而扫描单调栈巧妙运用了该性质。对于前者，可以扩展至无法拼接的问题而后者不能，如给定排列 $p$，将原问题 $\mathrm{lcp}(i, j)$ 换成 $\mathrm{lcp}(p_i, p_j)$。对于后者，可以扩展至任意容易快速计算 $f$ 的情形，如 $(\mathrm{lcp}(i, j) \mathrm{lcs}(i, j)) ^ k$。

#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
constexpr int N = 1e5 + 5;
ull f[N], ans;
int n, k1, k2;
char s[N];
ull S1(ull x) {return x * (x + 1) / 2;}
ull S2(ull x) {return x * (x + 1) * (x + x + 1) / 6;}
int sa[N], rk[N], ork[N], buc[N], id[N], ht[N];
bool cmp(int a, int b, int w) {return ork[a] == ork[b] && ork[a + w] == ork[b + w];}
void build() {
  int m = 1 << 7, p = 0;
  for(int i = 1; i <= n; i++) buc[rk[i] = s[i]]++;
  for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
  for(int i = n; i; i--) sa[buc[rk[i]]--] = i;
  for(int w = 1; ; w <<= 1, m = p, p = 0) {
    for(int i = n - w + 1; i <= n; i++) id[++p] = i;
    for(int i = 1; i <= n; i++) if(sa[i] > w) id[++p] = sa[i] - w;
    memset(buc, 0, sizeof(buc));
    memcpy(ork, rk, sizeof(rk)), p = 0;
    for(int i = 1; i <= n; i++) buc[rk[i]]++;
    for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
    for(int i = n; i; i--) sa[buc[rk[id[i]]]--] = id[i];
    for(int i = 1; i <= n; i++) rk[sa[i]] = cmp(sa[i - 1], sa[i], w) ? p : ++p;
    if(p == n) break;
  }
  for(int i = 1, k = 0; i <= n; i++) {
    if(k) k--;
    while(s[i + k] == s[sa[rk[i] - 1] + k]) k++;
    ht[rk[i]] = k;
  }
}
ull calc(char lim) {
  static int stc[N], w[N], top;
  ull cur = 0, ans = top = 0;
  for(int i = 2; i <= n; i++) {
    int wid = lim ? s[sa[i - 1] - 1] == lim : 1;
    while(top && stc[top] >= ht[i]) cur -= w[top] * f[stc[top]], wid += w[top--];
    stc[++top] = ht[i], w[top] = wid, cur += wid * f[ht[i]];
    if(lim ? s[sa[i] - 1] == lim : 1) ans += cur;
  }
  return ans;
}
int main() {
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  cin >> s + 1 >> k1 >> k2, n = strlen(s + 1);
  for(int L = 1; L <= n; L++) {
    int l = max(1, L - k2 + 1), r = min(L, k1);
    if(l > r) break;
    f[L] = (S1(r) - S1(l - 1)) * (L + 1) - (S2(r) - S2(l - 1));
  }
  build(), ans += calc(0);
  for(int i = 0; i < 26; i++) ans -= calc('a' + i);
  cout << ans << "\n";
  return 0;
}