CF1098F Ж-function

【题意】
给你一个字符串$s$，每次询问给你$l,r$，让你输出$ss=s_{l,r}$中${\sum }_{i=1}^{r-l+1}LCP(s{s}_i,s{s}_1)$。

【思路】
和前一道题一样，用了根号做法。

可以把贡献拆成两部分，第一部分是求原串中的LCP之和，显然这样有一些超过 $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 < rl++;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 >= rt = 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;
}