大型网站seo方法,网站引导页是什么,百度seo有用吗,谷歌网页版登录入口【题意】 给你一个字符串 s s s#xff0c;每次询问给你 l , r l, r l,r#xff0c;让你输出 s s s l , r sss_{l,r} sssl,r中 ∑ i 1 r − l 1 L C P ( s s i , s s 1 ) \sum_{i1}^{r-l1}LCP(ss_i,ss_1) ∑i1r−l1LCP(ssi,ss1)。
【思路】 和前一道题一样#…【题意】 给你一个字符串 s s s每次询问给你 l , r l, r l,r让你输出 s s s l , r sss_{l,r} sssl,r中 ∑ i 1 r − l 1 L C P ( s s i , s s 1 ) \sum_{i1}^{r-l1}LCP(ss_i,ss_1) ∑i1r−l1LCP(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];
vectorpairint, int ask[N];
ll ans[N];
int val[N], hsh[N];
int period[N], nxt[N], jump[N], to[N], f[N];void SA() {vectorint 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;}mapint, 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;
}
