bzoj3238 差异(后缀数组+单调栈)(Bzoj3238 difference (suffix array + monotone stack))

题目链接

解题思路

前面的部分可以直接求,关键是如何快速求后半部分。
我们知道两个后缀之间的lcp即他们之间的height数组的最小值。由于题目是对不同的数对计数,我们可以把后缀按照rk重新排序,每次计算当前的后缀j与它前面的后缀i的lcp,不难发现从j到i的过程中对height取min,得到的最小值是一块一块的。
我们可以用单调栈算出每一块以当前下标j为右端点,以height[j]为区间最小值能扩展到的最小左端点l[j],然后用dp的思想就能根据l[j]递推出当前的后缀与排名在他前面的后缀的lcp之和。

代码

const int maxn = 1e6+10;
int n, m;
char s[maxn];
int sa[maxn], x[maxn], y[maxn], c[maxn], rk[maxn], h[maxn];
void get_sa() {
    for (int i = 1; i<=n; ++i) ++c[x[i]=s[i]];
    for (int i = 2; i<=m; ++i) c[i] += c[i-1];
    for (int i = n; i; --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 = 1; i<=m; ++i) c[i] += c[i-1];
        for (int i = n; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 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;
    }
}
void get_h() {
    for (int i = 1; i<=n; ++i) rk[sa[i]] = i;
    for (int i = 1, k = 0; 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;
        h[rk[i]] = k;
    }
}
stack<int> sk;
int l[maxn]; ll lcp[maxn];
int main() { 
    IOS;
    cin >> s+1;
    n = strlen(s+1); m = 122;
    get_sa(); get_h();
    h[0] = -1;
    for (int i = n; i>=0; --i) {
        while(!sk.empty() && h[sk.top()]>h[i]) {
            l[sk.top()] = i;
            sk.pop();
        }
        sk.push(i);
    }
    ll sum = 0;
    for (int i = 1; i<=n; ++i) {
        lcp[i] = lcp[l[i]]+2LL*(i-l[i])*h[i];
        sum += 1LL*(n-1)*(n-i+1)-lcp[i];
    }
    cout << sum << endl;
    return 0;   
} 
————————

Title Link

Problem solving ideas

The front part can be solved directly. The key is how to quickly solve the second half.
We know the LCP between the two suffixes, that is, the minimum value of the height array between them. Since the topic is to count different pairs of numbers, we can reorder the suffixes according to rk. Each time we calculate the LCP of the current suffix J and the suffix I in front of it, it is not difficult to find that the minimum value obtained by taking min for height in the process from J to I is piece by piece.
We can use the monotone stack to calculate the minimum left endpoint l [J] that can be extended to each block with the current subscript j as the right endpoint and height [J] as the minimum value of the interval, and then use the idea of DP to deduce the sum of the current suffix and the LCP of the suffix in front of him according to l [J].

code

const int maxn = 1e6+10;
int n, m;
char s[maxn];
int sa[maxn], x[maxn], y[maxn], c[maxn], rk[maxn], h[maxn];
void get_sa() {
    for (int i = 1; i<=n; ++i) ++c[x[i]=s[i]];
    for (int i = 2; i<=m; ++i) c[i] += c[i-1];
    for (int i = n; i; --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 = 1; i<=m; ++i) c[i] += c[i-1];
        for (int i = n; i; --i) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 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;
    }
}
void get_h() {
    for (int i = 1; i<=n; ++i) rk[sa[i]] = i;
    for (int i = 1, k = 0; 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;
        h[rk[i]] = k;
    }
}
stack<int> sk;
int l[maxn]; ll lcp[maxn];
int main() { 
    IOS;
    cin >> s+1;
    n = strlen(s+1); m = 122;
    get_sa(); get_h();
    h[0] = -1;
    for (int i = n; i>=0; --i) {
        while(!sk.empty() && h[sk.top()]>h[i]) {
            l[sk.top()] = i;
            sk.pop();
        }
        sk.push(i);
    }
    ll sum = 0;
    for (int i = 1; i<=n; ++i) {
        lcp[i] = lcp[l[i]]+2LL*(i-l[i])*h[i];
        sum += 1LL*(n-1)*(n-i+1)-lcp[i];
    }
    cout << sum << endl;
    return 0;   
}