题目链接。
Description
给一个长度为 (n) 的字符串。每个下标有一个权值。
若以 (p) 开头的后缀与以 (q) 开头的后缀有长度为 (r) 的公共子串，则称这 (p, q) 是 (r) 相似的，并且可以获得 (a_p imes a_q) 的价值。
对于每个 (0 le r le n - 1)，求：
- 能选出来的 (p, q) 的方案数
- 最大价值
Solution
显然先搞一个后缀数组，然后对于 (x = lcp(p, q)) （(lcp) 是最长公共前缀的长度），它的相似度 (r) 可取 (0 le r le x)。
第一问
求方案数，即对于 (r) 的答案是：
（其中 ([x]) 表示 (x) 为真则为 (1)，否则为 (0)）。
我们设 (g_i = sum_{1 le i < j le n} [r = lcp(i, j)]) ，即表示 (lcp = i) 的对数。
那么 (Ans_r = sum_{i=r}^{n - 1} g_i)，即一个后缀和的形式。
所以问题转换为了 (g_i) 怎么求，我们用 (height) 数组转化一下：
(lcp(i, j) = min(height_{i + 1, i+2,...,j}))。
所以问题变成了求满足 (2 le i le j le n) ，(min(height_i, height_{i + 1}, height_{j}) = k) 的对数。这有很多做法，比如单调栈、涨水法，二分边界等。
我的想法是代表元计数法，对于 (min(height_{i, i + 1, ..., j}) = k) 的贡献记录在从左到右第一个值是 (k) 的身上。反推一下，对于一个 (i) 考虑他作为答案的代表元，找到左边第一个 (ge) 它的数下标 (L)，右边第一个 (>) 它的数下标 (R)。那么区间 ([L + 1, R - 1]) 是它的力所能及的范围，左端点可取([L + 1, i - 1])，右端点可取 ([i, R - 1])，方案数是两者的乘积。关于左边第一个大于等于他、右边第一个大于这种东西可以 (ST) 表 + 二分边界或者单调栈都是可以的。写单调栈不熟练这里直接写的前者。
第二问
跟第一问类似，把贡献区间算出来。然后就是左边区间选个数，右边选个数，然后两个权值乘积最大。注意这里有坑，最大值可能是两个最大正数的乘积，也有可能是两个最小整数的乘积，所以要两者取最优！
时间复杂度
(O(Nlog_2N))
Code
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int N = 300005, L = 19;
typedef long long LL;
int n, m = 127, a[N], p, rk[N], oldrk[N << 1], id[N], sa[N];
int cnt[N], height[N], f[N][L], Max[N][L], Min[N][L], Log[N];
LL sum[N], ans[N];
char s[N];
bool inline cmp(int i, int j, int k) {
return oldrk[i] == oldrk[j] && oldrk[i + k] == oldrk[j + k];
}
void inline SA() {
for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
for (int i = 2; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i; i--) sa[cnt[rk[i]]--] = i;
for (int w = 1; w < n; w <<= 1, m = p) {
p = 0;
for (int i = n; i > n - w; i--) id[++p] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > w) id[++p] = sa[i] - w;
for (int i = 1; i <= m; i++) cnt[i] = 0;
for (int i = 1; i <= n; i++) cnt[rk[i]]++;
for (int i = 2; i <= m; i++) cnt[i] += cnt[i - 1];
for (int i = n; i; i--) sa[cnt[rk[id[i]]]--] = id[i], oldrk[i] = rk[i];
p = 0;
for (int i = 1; i <= n; i++)
rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
}
for (int i = 1; i <= n; i++) {
int j = sa[rk[i] - 1], k = max(0, height[rk[i - 1]] - 1);
while (s[i + k] == s[j + k]) k++;
height[rk[i]] = k;
}
}
void inline ST_prework() {
for (int i = 1; i <= n; i++) {
f[i][0] = height[i], Log[i] = log2(i);
Max[i][0] = Min[i][0] = a[sa[i]];
}
for (int j = 1; j <= Log[n]; j++) {
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
}
}
}
int inline query(int l, int r) {
int k = Log[r - l + 1];
return min(f[l][k], f[r - (1 << k) + 1][k]);
}
int inline queryMax(int l, int r) {
int k = Log[r - l + 1];
return max(Max[l][k], Max[r - (1 << k) + 1][k]);
}
int inline queryMin(int l, int r) {
int k = Log[r - l + 1];
return min(Min[l][k], Min[r - (1 << k) + 1][k]);
}
int inline get1(int l, int r, int val) {
int i = r;
while (l < r) {
int mid = (l + r) >> 1;
if (query(mid, i - 1) > val) r = mid;
else l = mid + 1;
}
return r;
}
int inline get2(int l, int r, int val) {
int i = l;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (query(i, mid) >= val) l = mid;
else r = mid - 1;
}
return r;
}
int main() {
scanf("%d%s", &n, s + 1);
for (int i = 1; i <= n; i++) scanf("%d", a + i), ans[i - 1] = -9e18;
SA();
ST_prework();
for (int i = 2; i <= n; i++) {
int L = get1(2, i, height[i]), R = get2(i, n, height[i]);
// [L - 1 ~ i - 1, i ~ R]
if (L - 1 > i - 1) continue;
sum[height[i]] += (LL)(i - 1 - (L - 1) + 1) * (R - i + 1);
LL v1 = (LL)queryMax(L - 1, i - 1) * queryMax(i, R);
LL v2 = (LL)queryMin(L - 1, i - 1) * queryMin(i, R);
ans[height[i]] = max(ans[height[i]], max(v1, v2));
}
for (int i = n - 2; ~i; i--) sum[i] += sum[i + 1], ans[i] = max(ans[i], ans[i + 1]);
for (int i = 0; i < n; i++)
printf("%lld %lld
", sum[i], sum[i] == 0 ? 0 : ans[i]);
return 0;
}