Description
一个字符串 \(t\) 被称为字符串 \(w\) 的 平滑变换（smooth transformation），如果存在一个整数 \(m \ge 1\) 和一系列字符串
\(w_0, w_1, \ldots, w_m\)，满足以下条件：
- \(w_0 = w\)，并且当 \(0 < i \le m\) 时，\(|w_i| = |w|\)；
- 当 \(0 < i \le m\) 时，\(w_i\) 与 \(w_{i-1}\) 至多在一个位置上不同；
- \(t = w_0 w_1 \ldots w_m\)。
现在给定一个字符串 \(s = s_1 s_2 \ldots s_{|s|}\)，要求计算满足 \(1 \le i < j < k \le |s|\) 且 \(s_{i..k} = s_i s_{i+1} \ldots s_k\) 是 \(s_{i..j} = s_i s_{i+1} \ldots s_j\) 的平滑变换的三元组 \((i, j, k)\) 的数量。
\(n\leq 10^5\)。
Solution
首先容易发现对于 \(|w_0|\) 不同的串，它们之间是没有多大的联系的，所以考虑对于 \(|w_0|\) 相同的一起做。
现在钦定 \(|w_i|\) 都是 \(L\)，我们根据 NOI2016 优秀的拆分 的思路，对序列按照长度 \(L\) 分块，定义形如 \(kL\) 的点为关键点。
那么每个可能的 \(w_i\) 都一定恰好包含一个关键点，考虑枚举这个关键点。
设 \(w_i\) 的起点是 \(p\)，\([p,p+L-1]\) 经过的关键点是 \(x\)，同时定义：
- \(\text{LCP}(s_1,s_2)\) 为 \(s_1,s_2\) 的最长公共前缀。
- \(\text{LCS}(s_1,s_2)\) 为 \(s_1,s_2\) 的最长公共后缀。
- \(\text{LCP}'(s_1,s_2)\) 为 \(s_1,s_2\) 至多有一个位置字符不同的最长公共前缀。
- \(\text{LCS}'(s_1,s_2)\) 为 \(s_1,s_2\) 至多有一个位置字符不同的最长公共后缀。
然后分讨 \([p,p+L-1]\) 和 \([p+L,p+2L-1]\) 不同的位置：
-
如果位置在 \([p,x]\) 之间，则形如
此时需要满足 \(\text{LCS}'(s_{[1,x]},s_{1,x+L})\geq p-k+1,\text{LCP}(s_{[x+1,n]},s_{x+L+1,n})\geq p+L-1-x\)。
-
如果位置在 \([x+1,p+L-1]\) 之间，形如
需要满足 \(\text{LCS}(s_{[1,x]},s_{1,x+L})\geq p-k+1,\text{LCP}'(s_{[x+1,n]},s_{x+L+1,n})\geq p+L-1-x\)。
容易发现对于相同的 \(x\)，\(p\) 的限制实际上是一样的，所以暴力枚举 \(x\)，可以得到包含 \(x\) 的长度为 \(L\) 的区间 \([p,p+L-1]\) 中，能与 \([p+L,p+2L-1]\) 接上的 \(p\) 的范围。
由于所有 \(w_i\) 开头的位置\(\bmod L\) 相同，所以从后往前维护一个关于余数的线段树即可。
时间复杂度：\(O(n\log n)/O(n\log^2n)\)，取决于求 \(\text{LCP}/\text{LCS}/\text{LCP}'/\text{LCS}'\) 是用哈希加二分还是后缀数组。
具体细节见代码。
Code
#include <bits/stdc++.h>#define int int64_tusing u64 = uint64_t;const int kMaxN = 1e5 + 5, kMod = 998244353;int n;
int hs[kMaxN], pw[kMaxN];
std::string str;struct SGT {int sum[kMaxN * 4], tagc[kMaxN * 4], taga[kMaxN * 4];void pushup(int x) { sum[x] = sum[x << 1] + sum[x << 1 | 1]; }void addtagc(int x, int l, int r, int v) { sum[x] = 1ll * v * (r - l + 1), tagc[x] = v, taga[x] = 0; }void addtaga(int x, int l, int r, int v) { sum[x] += 1ll * v * (r - l + 1), taga[x] += v; }void pushdown(int x, int l, int r) {int mid = (l + r) >> 1;if (tagc[x] != -1) addtagc(x << 1, l, mid, tagc[x]), addtagc(x << 1 | 1, mid + 1, r, tagc[x]), tagc[x] = -1;if (taga[x]) addtaga(x << 1, l, mid, taga[x]), addtaga(x << 1 | 1, mid + 1, r, taga[x]), taga[x] = 0;}void build(int x, int l, int r) {sum[x] = taga[x] = 0, tagc[x] = -1;if (l == r) return;int mid = (l + r) >> 1;build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);}void updatec(int x, int l, int r, int ql, int qr, int v) {if (l > qr || r < ql) return;else if (l >= ql && r <= qr) return addtagc(x, l, r, v);pushdown(x, l, r);int mid = (l + r) >> 1;updatec(x << 1, l, mid, ql, qr, v), updatec(x << 1 | 1, mid + 1, r, ql, qr, v);pushup(x);}void updatea(int x, int l, int r, int ql, int qr, int v) {if (l > qr || r < ql) return;else if (l >= ql && r <= qr) return addtaga(x, l, r, v);pushdown(x, l, r);int mid = (l + r) >> 1;updatea(x << 1, l, mid, ql, qr, v), updatea(x << 1 | 1, mid + 1, r, ql, qr, v);pushup(x);}int query(int x, int l, int r, int ql, int qr) {if (l > qr || r < ql) return 0;else if (l >= ql && r <= qr) return sum[x];pushdown(x, l, r);int mid = (l + r) >> 1;return query(x << 1, l, mid, ql, qr) + query(x << 1 | 1, mid + 1, r, ql, qr);}
} sgt;void prework() {pw[0] = 1;for (int i = 1; i <= n; ++i) {pw[i] = 13331ll * pw[i - 1] % kMod;hs[i] = (13331ll * hs[i - 1] + str[i]) % kMod;}
}u64 gethash(int l, int r) { return (hs[r] - 1ll * hs[l - 1] * pw[r - l + 1] % kMod + kMod) % kMod; }int LCP(int x, int y) {if (x < 1 || y < 1 || x > n || y > n) return 0;int L = 0, R = n - std::max(x, y) + 2, res = 0;while (L + 1 < R) {int mid = (L + R) >> 1;if (gethash(x, x + mid - 1) == gethash(y, y + mid - 1)) L = res = mid;else R = mid;}return res;
}int _LCP(int x, int y) {if (x < 1 || y < 1 || x > n || y > n) return 0;int lim = n - std::max(x, y) + 1, lcp = LCP(x, y);if (std::max(x, y) + lcp + 1 <= n) return lcp + 1 + LCP(x + lcp + 1, y + lcp + 1);else return std::min(lcp + 1, lim);
}int LCS(int x, int y) {if (x < 1 || y < 1 || x > n || y > n) return 0;int L = 0, R = std::min(x, y) + 1, res = 0;while (L + 1 < R) {int mid = (L + R) >> 1;if (gethash(x - mid + 1, x) == gethash(y - mid + 1, y)) L = res = mid;else R = mid;}return res;
}int _LCS(int x, int y) {if (x < 1 || y < 1 || x > n || y > n) return 0;int lim = std::min(x, y), lcs = LCS(x, y);if (std::min(x, y) - lcs - 1 >= 1) return lcs + 1 + LCS(x - lcs - 1, y - lcs - 1);else return std::min(lcs + 1, lim);
}void dickdreamer() {std::cin >> str;n = str.size(), str = " " + str;prework();int ans = 0;sgt.build(1, 1, n);for (int L = 2; L <= n; ++L) {sgt.updatec(1, 1, n, 1, n, 0);for (int p = L * (n / L); p; p -= L) {if (p + L > n) {int l = 1, r = n - p + 1;ans += sgt.query(1, 1, n, l, r), sgt.updatea(1, 1, n, l, r, 1);} else {int l1 = p - _LCS(p, p + L) + 1, r1 = p + LCP(p + 1, p + L + 1) - L + 1;int l2 = p - LCS(p, p + L) + 1, r2 = p + _LCP(p + 1, p + L + 1) - L + 1;l1 -= p - L, r1 -= p - L, l2 -= p - L, r2 -= p - L;l1 = std::max<int>(l1, 1), r1 = std::min(r1, L);l2 = std::max<int>(l2, 1), r2 = std::min(r2, L);if (std::max(l1, l2) <= std::min(r1, r2)) {int l = std::min(l1, l2), r = std::max(r1, r2);ans += sgt.query(1, 1, n, l, r), sgt.updatea(1, 1, n, l, r, 1);sgt.updatec(1, 1, n, 1, l - 1, 1), sgt.updatec(1, 1, n, r + 1, L, 1);} else {if (l1 > l2) std::swap(l1, l2), std::swap(r1, r2);if (l1 <= r1 && l2 <= r2) {assert(r1 < l2);ans += sgt.query(1, 1, n, l1, r1), sgt.updatea(1, 1, n, l1, r1, 1);ans += sgt.query(1, 1, n, l2, r2), sgt.updatea(1, 1, n, l2, r2, 1);sgt.updatec(1, 1, n, 1, l1 - 1, 1), sgt.updatec(1, 1, n, r1 + 1, l2 - 1, 1), sgt.updatec(1, 1, n, r2 + 1, L, 1);} else if (l1 <= r1) {ans += sgt.query(1, 1, n, l1, r1), sgt.updatea(1, 1, n, l1, r1, 1);sgt.updatec(1, 1, n, 1, l1 - 1, 1), sgt.updatec(1, 1, n, r1 + 1, L, 1);} else if (l2 <= r2) {ans += sgt.query(1, 1, n, l2, r2), sgt.updatea(1, 1, n, l2, r2, 1);sgt.updatec(1, 1, n, 1, l2 - 1, 1), sgt.updatec(1, 1, n, r2 + 1, L, 1);} else {sgt.updatec(1, 1, n, 1, L, 1);}}}}}std::cout << ans << '\n';
}int32_t main() {
#ifdef ORZXKRfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifstd::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);int T = 1;// std::cin >> T;while (T--) dickdreamer();// std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";return 0;
}