BZOJ3238 [Ahoi2013]差异

//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
using LL = int_fast64_t;
const int MAXN = 5e5+7;
struct SA{
    int sa[MAXN],rk[MAXN],c[MAXN],sec[MAXN],height[MAXN],n;
    char s[MAXN];
    void getsa(int m){
        n = strlen(s+1);
        for(int i = 0; i <= m; i++) c[i] = 0;
        for(int i = 1; i <= n; i++) c[rk[i]=s[i]]++;
        for(int i = 1; i <= m; i++) c[i] += c[i-1];
        for(int i = n; i >= 1; i--) sa[c[rk[i]]--] = i;
        for(int k = 1; k <= n; k <<= 1){
            int p = 0;
            for(int i = n - k + 1; i <= n; i++) sec[++p] = i;
            for(int i = 1; i <= n; i++) if(sa[i]>k) sec[++p] = sa[i] - k;
            for(int i = 0; i <= m; i++) c[i] =  0;
            for(int i = 1; i <= n; i++) c[rk[sec[i]]]++;
            for(int i = 1; i <= m; i++) c[i] += c[i-1];
            for(int i = n; i >= 1; i--) sa[c[rk[sec[i]]]--] = sec[i];
            p = 0;
            swap(rk,sec);
            rk[sa[1]] = ++p;
            for(int i = 2; i <= n; i++) rk[sa[i]] = sec[sa[i]]==sec[sa[i-1]] and sec[sa[i]+k]==sec[sa[i-1]+k] ? p : ++p;
            if(p==n) break;
            m = p;
        }
    }
    void getheight(){
        int k = 0;
        for(int i = 1; i <= n; i++){
            if(k) k--;
            int j = sa[rk[i]-1];
            while(s[i+k]==s[j+k]) k++;
            height[rk[i]] = k;
        }
    }
    LL solve(){
        getsa(128);
        getheight();
        LL ret = (n+1ll) * n * (n-1ll) / 2;
        stack<pair<int,int> > stk;
        LL tot = 0;
        for(int i = 1; i <= n; i++){
            int num = 1;
            while(!stk.empty() and height[i]<=height[stk.top().first]){
                num += stk.top().second;
                tot -= 1ll * stk.top().second * (height[stk.top().first] - height[i]);
                stk.pop();
            }
            stk.push(make_pair(i,num));
            tot += height[i];
            ret -= tot * 2;
        }
        return ret;
    }
}sa;
char s[MAXN];
int main(){
    scanf("%s",sa.s+1);
    printf("%lld\n",sa.solve());
    return 0;
}

BZOJ3238 [Ahoi2013]差异

原文：https://www.cnblogs.com/kikokiko/p/12713059.html