P5115 Check, Check, Check one two!

Alex_Wei · 2022-11-05 08:09:38 · 题解

看到题目，我首先想到建出正反串 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;
}