Can You Solve the Harder Problem?（2018ICPC焦作H）（后缀自动机+单调栈）

Can You Solve the Harder Problem?

这题简直妙呀！可惜训练赛的时候 $3h$3h我们就以为开不了题了。。。因此 $3h$3h后 $5$5题离场。。。吃完饭回来看了这题题解，看到了 $Suffix$Suffix $structures$structures后秒懂！而且代码也简单！

这题主要利用了后缀自动机的每个节点可以表达出原串本质不同的所有子串！这点非常巧妙！

题意：将给定的数组想象成字符串，若考虑每个子串的贡献为其最大的字符的值，则要求原串（数组）中所有本质不同的子串的贡献之和（能将原题等价为这样的题意就基本可以做出来了，但是想不到。。。）

思路：

1. 若直接建立后缀自动机（转移边用 $map$map来存）（ $O\left(nlogn\right)+$O(nlogn)+大常数），则在后续依次计算每个节点的贡献时，会发现每个节点都可能代表 $O\left(n\right)$O(n)个子串，并且每次求子串的最大值复杂度都是 $O\left(logn\right)$O(logn)的（线段树或者树状数组），而后缀自动机最多有 $2n$2n个节点，因此这样复杂度是 $O\left(n^{2}logn\right)$O(n2logn)的，这样的复杂度显然无法接受。
2. 但是仔细思考，在构建后缀自动机时，每次在尾部增加一个字符（第 $i$i个字符），最多增加 $i$i个本质不同的子串。这些子串都是以 $a\left[i\right]$a[i]结尾的，若新增节点的 $father$father存在，则新增了 $len\left[np\right]-len\left[fa\right[np\left]\right]$len[np]−len[fa[np]]个本质不同的子串，然后我们只需要计算这些子串的贡献即可。
3. 在计算过程中，若在原数组上动态的维护一个单调递减的栈，则栈中每个数代表了原串中某一段当前后缀的最大值，然后。。。再然后（代码中那个前缀和是加速的关键）。。。最后就。。。复杂度变成了 $O\left(nlogn\right)+$O(nlogn)+大常数啦！
4. 好吧，已经说不清楚了，反正很妙，很美，写出来就很爽！（个人感觉写得还挺短的，代码加上注释后应该比较清晰）（没看过别人写的，不知道有没有更好的解法）

题面描述

#include "bits/stdc++.h"
#include <unordered_map>
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 4e5+10;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-7;

int n;
int a[maxn];
int stk[maxn], idx[maxn], top;
int fa[maxn], len[maxn];
unordered_map<int,int> ch[maxn];
int last, tot;
ll pre[maxn], ans;

void init() {
    for(int i=1; i<=tot; ++i) ch[i].clear(), fa[i]=0;
    last=tot=1, top=0, ans=0;
}

void add(int c, int pos) {
    int p=last, np=last=++tot;
    len[np]=len[p]+1;
    for(; p&&!ch[p][c]; p=fa[p]) ch[p][c]=np;
    if(!p) fa[np]=1;
    else {
        int q=ch[p][c];
        if(len[q]==len[p]+1) fa[np]=q;
        else {
            int nq=++tot;
            fa[nq]=fa[q], len[nq]=len[p]+1, ch[nq]=ch[q];
            fa[np]=fa[q]=nq;
            for(; p&&ch[p][c]==q; p=fa[p]) ch[p][c]=nq;
        }
    } //前面是普通的后缀自动机，下面是统计加入当前字符后新增本质不同的子串对答案的贡献
    int st=len[np]-len[fa[np]]; //新增的本质不同的串的首字符下标从1到st，尾字符都是当前新增字符
    int l=1, r=top, m=(l+r)/2; //计算从哪里开始利用前缀和，利用前缀和就是加速的关键！我也不知道我怎么想到的，简直妙呀！
    while(l<r) {
        if(idx[m]>=st) r=m;
        else l=m+1;
        m=(l+r)/2;
    }
    ans+=pre[m-1]+1ll*stk[m]*(st-idx[m-1]); //这个答案统计就简单啦
}

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    int T=read();
    while(T--) {
        init();
        int n=read();
        for(int i=1; i<=n; ++i) a[i]=read();
        for(int i=1; i<=n; ++i) {
            while(top&&stk[top]<=a[i]) top--;
            ++top, stk[top]=a[i], idx[top]=i, pre[top]=pre[top-1]+1ll*a[i]*(idx[top]-idx[top-1]); //维护单调栈，并且记录单调栈中每个数在原串中的下标，再记录单调栈中每个数到栈底对答案的贡献，也就是一个前缀和（这一点不好理解）
            add(a[i],i);
        }
        printf("%lld\n", ans);
    }
}