题目链接。

Description

给一个长度为 \(n\) 的字符串。每个下标有一个权值。

若以 \(p\) 开头的后缀与以 \(q\) 开头的后缀有长度为 \(r\) 的公共子串，则称这 \(p, q\) 是 \(r\) 相似的，并且可以获得 \(a_p \times a_q\) 的价值。

对于每个 \(0 \le r \le n - 1\)，求：

• 能选出来的 \(p, q\) 的方案数
• 最大价值

Solution

显然先搞一个后缀数组，然后对于 \(x = lcp(p, q)\) （\(lcp\) 是最长公共前缀的长度），它的相似度 \(r\) 可取 \(0 \le r \le x\)。

第一问

求方案数，即对于 \(r\) 的答案是：

\[Ans_r = \sum_{1 \le i < j \le n} [r <= lcp(i, j)] \]（其中 \([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(N\log_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\n", sum[i], sum[i] == 0 ? 0 : ans[i]);
    return 0;
}

NOI2015 品酒大会

原文：https://www.cnblogs.com/dmoransky/p/12513382.html