题解：P7409 SvT
LostKeyToReach
·
·
题解
哈哈，最近加训字符串题。
我们要求的式子为：
\sum_{i = 1} ^ K \sum_{j = i + 1} ^ K \text{LCP}(s_i, s_j).
其中 s_i 表示以 i 为起点的后缀，K 为后缀集合的长度，记得需要去重。
然后我们计算一下 \text{SA} 数组和 \text{height} 数组，然后化简原式：
\begin{aligned}
\sum_{i = 1} ^ K \sum_{j = i + 1} ^ K \text{LCP}(s_i, s_j) &= \sum_{i = 1} ^ K \sum_{j = i + 1} ^ K \min_{r_i + 1 \le k \le r_j} \{\text{height}_k\}.
\end{aligned}
这个东西是一个很典型的求和问题，我们再转换一下，先令 $f_i = \min_{r_{i - 1} + 1 \le k \le r_i}\{\text{height}_k\}$，然后把原式转换为：
$$
\sum_{1 \le i < j \le K} \min_{i \le k \le j} \{f_i\}.
$$
$f_i$ 可以 ST 表预处理，然后拿单调栈做就行啦。
时间复杂度 $O(n \log n + \sum t \log t)$。
AC 代码（仅供参考，若需要理解可以格式化）：
```cpp
#include <bits/stdc++.h>
#define int long long
#define vi vt<int>
#define S std::ios::sync_with_stdio(0), \
std::cin.tie(0), std::cout.tie(0)
using ll = long long;
using pii = std::pair<int, int>;
template<typename T> using vt = std::vector<T>;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define For(i, a, b) for(int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for(int i = (a); i >= (b); --i)
template<typename T> T chkmax(T& x, T y) {
return (x < y) ? (x = y, y) : x;
} template<typename T> T chkmin(T& x, T y) {
return (x > y) ? (x = y, y) : x; }
int fio = (S, 0); constexpr int N = 5e5 + 5, mod = 23333333333333333LL;
int sa[N], rk[20][N], tmp[N], buc[N], len, h[N], st[20][N];
int32_t main() {/*freopen("D:\\BaiduNetdiskDownload\\P7409_1.in", "r", stdin); */int n, m, kk; std::cin >> n >> m;
std::string s; std::cin >> s; For(i, 1, n) buc[rk[0][i] = s[i - 1]] += 1;
For(i, 1, 255) buc[i] += buc[i - 1]; Rof(i, n, 1) sa[buc[rk[0][i]]--] = i;
for (int k = 1, p, v; (1 << (k - 1)) < n; ++k) {
v = (1 << (k - 1)), p = 0; For(i, n - v + 1, n) tmp[++p] = i;
For(i, 1, n) if (sa[i] > v) tmp[++p] = sa[i] - v; std::fill(buc, buc + n + 1, 0);
For(i, 1, n) buc[rk[k - 1][i]]++; For(i, 1, n) buc[i] += buc[i - 1];
Rof(i, n, 1) sa[buc[rk[k - 1][tmp[i]]]--] = tmp[i]; rk[k][sa[1]] = p = 1;
For(i, 2, n) if (rk[k][sa[i]] = p, rk[k - 1][sa[i]] != rk[k - 1][sa[i - 1]]) ++p, ++rk[k][sa[i]];
else if (rk[k - 1][sa[i] + v] != rk[k - 1][sa[i - 1] + v]) ++p, ++rk[k][sa[i]];
if (p == n) break;
} len = log2(n); vi ss(n + 1, 0), lg(n + 1, 0); ss[sa[1]] = 1; For(i, 2, n) ss[sa[i]] = i, lg[i] = lg[i >> 1] + 1;
for (int i = 1, j = 0; i <= n; ++i) {if (ss[i] < 2) continue; kk = sa[ss[i] - 1];
while (j <= std::min(n - i, n - kk) && s[i + j - 1] == s[kk + j - 1]) j++; h[ss[i]] = j, j -= !!j;
} For(i, 1, n) st[0][i] = h[i]; For(k, 1, 19) if ((1 << k) <= n) {
For(i, 1, n - (1 << k) + 1) st[k][i] = std::min(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
} auto query = [&](int l, int r) -> int {if (l > r) std::swap(l, r); if (l == r) return n - sa[l] + 1;
return (++l, kk = lg[r - l + 1], std::min(st[kk][l], st[kk][r - (1 << kk) + 1]));};
while (m--) {int t; std::cin >> t; vi pos(t); For(i, 0, t - 1) std::cin >> pos[i];
std::sort(all(pos)), pos.erase(std::unique(all(pos)), pos.end()); int k = sz(pos);
if (k < 2) std::cout << "0\n"; else {vi f(k); For(i, 0, k - 1) f[i] = ss[pos[i]]; std::sort(all(f));
vi b(k), l = b, r = b;For(i, 1, k - 1) b[i] = query(f[i - 1], f[i]); std::stack<int> stk;
For(i, 1, k - 1) {while (!stk.empty() && b[stk.top()] >= b[i]) stk.pop();
l[i] = stk.empty() ? 0 : stk.top(); stk.emplace(i);} while (!stk.empty()) stk.pop();
Rof(i, k - 1, 1) { while (!stk.empty() && b[stk.top()] > b[i]) stk.pop();
r[i] = stk.empty() ? k : stk.top(); stk.emplace(i);
} int ans = 0; For(i, 1, k - 1) (ans += (i - l[i]) * (r[i] - i) * b[i] % mod) %= mod;
std::cout << ans << "\n"; /*OI 2025 RP+++*/}} return 0;
}
```