CF1098F Ж-function
【题意】
给你一个字符串
s
s
s，每次询问给你
l
,
r
l, r
l,r，让你输出
s
s
=
s
l
,
r
ss=s_{l,r}
ss=sl,r中
∑
i
=
1
r
−
l
+
1
L
C
P
(
s
s
i
,
s
s
1
)
\sum_{i=1}^{r-l+1}LCP(ss_i,ss_1)
∑i=1r−l+1LCP(ssi,ss1)。
【思路】
和前一道题一样，用了根号做法。
可以把贡献拆成两部分，第一部分是求原串中的LCP之和，显然这样有一些超过 r r r，而这些都是border，然后就用[BJWC2018] Border 的四种求法的方法来修正这一部分的贡献即可。
第一部分先用SA，然后正着扫反着扫用分块维护。
第二部分就在前一题的基础上多进行一些对长度的分类讨论就行。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10, B = 250;
const int mod = 1e9 + 7;
int n, m; char s[N];
int sa[N], rk[N], height[N], st[N][20], lg[N];
vector<pair<int, int>> ask[N];
ll ans[N];
int val[N], hsh[N];
int period[N], nxt[N], jump[N], to[N], f[N];
void SA() {
vector<int> x(N), y(N), c(N);
int m = 256;
for (int i = 1; i <= n; i++) c[x[i] = s[i]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
for (int k = 1; k <= n; k <<= 1) {
int num = 0;
for (int i = n - k + 1; i <= n; i++) y[++num] = i;
for (int i = 1; i <= n; i++) if (sa[i] > k) y[++num] = sa[i] - k;
for (int i = 1; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i]]++;
for (int i = 2; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
swap(x, y); x[sa[1]] = num = 1;
for (int i = 2; i <= n; i++)
x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
if (num == n) break;
m = num;
}
for (int i = 1; i <= n; i++) rk[sa[i]] = i;
int k = 0;
for (int i = 1; i <= n; i++) {
if (rk[i] == 1) continue;
if (k) k--;
int j = sa[rk[i] - 1];
while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++;
height[rk[i]] = k;
}
lg[0] = -1;
for (int i = 1; i <= n; i++) {
st[i][0] = height[i];
lg[i] = lg[i >> 1] + 1;
}
for (int j = 1; j <= 18; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
int getlcp(int i, int j) {
i = rk[i], j = rk[j];
if (i > j) swap(i, j);
i++;
int t = lg[j - i + 1];
return min(st[i][t], st[j - (1 << t) + 1][t]);
}
namespace block {
int cnt, L[N / B + 10], R[N / B + 10], belong[N];
int siz[N / B + 10], num[N / B + 10][B + 10], val[N / B + 10][B + 10];
ll sum[N / B + 10];
bool vis[N];
void init() {
cnt = 0;
memset(siz, 0, sizeof(siz));
memset(num, 0, sizeof(num));
memset(val, 0, sizeof(val));
memset(sum, 0, sizeof(sum));
memset(vis, 0, sizeof(vis));
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n, l + B - 1);
cnt++;
L[cnt] = l, R[cnt] = r;
for (int i = l; i <= r; i++) {
belong[i] = cnt;
}
}
}
void limit(int x) {
for (int i = 1; i <= cnt; i++) {
int tot = 0;
while (siz[i] && val[i][siz[i]] >= x) {
tot += num[i][siz[i]];
sum[i] -= 1ll * num[i][siz[i]] * val[i][siz[i]];
siz[i]--;
}
if (tot) {
siz[i]++;
num[i][siz[i]] = tot;
val[i][siz[i]] = x;
sum[i] += 1ll * tot * x;
}
}
}
ll calc(int l, int r) { // l < r
l++;
ll ret = 0;
if (belong[l] == belong[r]) {
for (int i = l; i <= r; i++) if (vis[i]) {
ret += getlcp(l - 1, i);
}
}
else {
int t;
t = belong[r];
for (int i = L[t]; i <= r; i++) if (vis[i]) {
ret += getlcp(l - 1, i);
}
r = L[t] - 1;
t = belong[l];
for (int i = l; i <= R[t]; i++) if (vis[i]) {
ret += getlcp(l - 1, i);
}
l = R[t] + 1;
while (l <= r) {
ret += sum[belong[l]];
l += B;
}
}
return ret;
}
void ins(int pos) {
vis[pos] = 1;
int len = n - pos + 1;
int t = belong[pos];
sum[t] += len;
for (int i = 1; i <= siz[t]; i++) {
if (val[t][i] == len) {
num[t][i]++;
return;
}
}
siz[t]++;
num[t][siz[t]] = 1;
val[t][siz[t]] = len;
for (int i = siz[t]; i > 1; i--) {
if (val[t][i] < val[t][i - 1]) {
swap(val[t][i], val[t][i - 1]);
swap(num[t][i], num[t][i - 1]);
}
else {
break;
}
}
}
}
int gethsh(int l, int r) {
return (hsh[r] - 1ll * hsh[l - 1] * val[r - l + 1] % mod + mod) % mod;
}
ll getsum(int a1, int d, int n) {
return 1ll * a1 * n - 1ll * d * n * (n - 1) / 2;
}
int main() {
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
clock_t start = clock();
cin >> (s + 1) >> m;
n = strlen(s + 1);
SA();
// for (int i = 1; i <= n; i++) {
// cout << sa[i] << " \n"[i == n];
// }
// for (int i = 1; i <= n; i++) {
// cout << height[i] << " \n"[i == n];
// }
for (int i = 1; i <= m; i++) {
int l, r; cin >> l >> r;
ans[i] = r - l + 1;
if (l < r) ask[l].push_back({r, i});
}
block::init();
for (int ki = 1; ki <= n; ki++) {
block::limit(height[ki]);
int l = sa[ki];
for (auto [r, id] : ask[l]) {
ans[id] += block::calc(l, r);
}
block::ins(l);
}
block::init();
height[n + 1] = 0;
for (int ki = n; ki >= 1; ki--) {
block::limit(height[ki + 1]);
int l = sa[ki];
for (auto [r, id] : ask[l]) {
ans[id] += block::calc(l, r);
}
block::ins(l);
}
val[0] = 1;
for (int i = 1; i <= n; i++) {
val[i] = 1ll * val[i - 1] * 257 % mod;
hsh[i] = (1ll * hsh[i - 1] * 257 + s[i] - 'a') % mod;
}
map<int, int> last;
for (int i = 1; i <= n; i++) nxt[i] = n + 1;
for (int ki = 1; ki <= n - B + 1; ki++) {
f[ki] = ki - 1;
for (int i = ki + 1, j = ki - 1; i <= ki + B - 1; i++) {
while (j > ki - 1 && s[j + 1] != s[i]) j = f[j];
if (s[j + 1] == s[i]) j++;
f[i] = j;
}
period[ki] = ki + B - 1 - f[ki + B - 1];
int now = gethsh(ki, ki + B - 1);
if (last[now]) nxt[last[now]] = ki;
last[now] = ki;
}
last.clear();
for (int i = 1; i <= n; i++) jump[i] = i;
for (int i = n - B + 2; i <= n + 1; i++) to[i] = n;
for (int i = n - B + 1; i >= 1; i--) {
int j = i + period[i];
if (j <= n && nxt[i] == j) to[i] = to[j], jump[i] = jump[j];
else {
for (int j = i + B - 1, k = i + (B - 1) % period[i]; j <= n; j++) {
if (s[j] != s[k]) break;
to[i] = j;
k++; if (k == i + period[i]) k = i;
}
}
}
// clock_t end = clock();
// cout << (double)(end - start) / CLOCKS_PER_SEC << endl;
for (int l = 1; l < n; l++) {
for (auto [r, id] : ask[l]) {
ll ret = 0;
if (r - l + 1 <= 2 * B) {
for (int i = l + 1; i <= r; i++) {
int t = r - i + 1;
if (gethsh(l, l + t - 1) == gethsh(i, r)) {
ret -= getlcp(l, i);
ret += t;
}
}
}
else {
for (int t = 1; t < B; t++) {
if (gethsh(l, l + t - 1) == gethsh(r - t + 1, r)) {
ret -= getlcp(l, r - t + 1);
ret += t;
}
}
int x = nxt[l];
int len = period[l];
int count = 0;
while (to[x] < r) {
// assert((++count) <= 500);
if (to[x] - x >= to[l] - l && (to[x] - x) % len == (to[l] - l) % len) {
x = to[x] - (to[l] - l);
int t = r - x + 1;
if (gethsh(l, l + t - 1) == gethsh(x, r)) {
ret -= getlcp(l, x);
ret += t;
}
}
x = nxt[jump[x]];
}
if (x + B - 1 <= r) {
int len1 = to[l] - l + 1;
int len2 = to[x] - x + 1;
//>
int t;
if (x + len1 - 1 < r) {
t = (r - x - len1) / len + 1;
x += t * len;
len2 -= t * len;
}
if (x + B - 1 <= r && len2 > len1) {
//x + len1 - 1 >= r
t = min(len2 - len1 - 1, r - B + 1 - x) / len + 1;
ret -= 1ll * (to[l] - l + 1) * t;
ret += getsum(r - x + 1, len, t);
len2 -= len * t;
x += len * t;
}
//==
if (x + B - 1 <= r && len1 == len2) {
ret -= getlcp(l, x);
ret += r - x + 1;
len2 -= len;
x += len;
}
//<
if (x + B - 1 <= r) {
t = (r - B + 1 - x) / len + 1;
ret += 1ll * (r - to[x]) * t;
}
}
}
ans[id] += ret;
}
}
// clock_t end2 = clock();
// cout << (double)(end2 - end) / CLOCKS_PER_SEC << endl;
// cout << (double)(end2 - start) / CLOCKS_PER_SEC << endl;
for (int i = 1; i <= m; i++) {
cout << ans[i] << "\n";
}
// clock_t end3 = clock();
// cout << (double)(end3 - start) / CLOCKS_PER_SEC << endl;
}