kyopro_friendsさんの解説 にもあるように、求める値は

\(A_i=f(S_i,S_{i+1})\) としたときの

\(\displaystyle \sum_{l=1}^{N-1}\sum_{r=l+1}^{N}{\min(A_l,A_{l+1},\dots,A_{r-1})}\)

と表せます。

\((A_i,i)\) の値の降順に \(A_i\) の答えへの寄与を求めます。このとき、

\(\min(A_{i+1},A_{i+2},A_{r-1})>A_i\) であり、かつ\(\min(A_l,A_{l+1},\dots,A_{r-1})=A_i\) となる \((l,r)\) は

\(L_i=(全ての k(x\leq k<i) についてすでに A_k の寄与を求めているような x としてありうる最小値)\)

\(R_i=(全ての k(i< k<x) についてすでに A_k の寄与を求めているような x としてありうる最大値)\)

としたとき\((A_i,i)\) の降順で走査をしていることから

\(\min(A_{L_i},A_{L_i+1},\dots,A_{i-1})>A_i\) 、 \(\min(A_{L_i-1},A_{L_i+1},\dots,A_{i-1})\leq A_i\)

\(\min(A_{i+1},A_{i+2},\dots,A_{R_i-1})\geq A_i\) 、 \(\min(A_{i+1},A_{i+2},\dots,A_{R_i})< A_i\)

が成り立ち、\(L_i\leq l\leq i<r\leq R_i\) は条件の必要十分条件より、

\((i-L_i+1)\cdot(R_i-i)\) 個あることがわかります。

また \(N\) 頂点のグラフにおいて \((A_i,i)\) の寄与を計算した後に 頂点\(i,i+1\) 間 を連結にする操作を考えると

\(L_i=i-(頂点iの連結成分)+1,R_i=i+(頂点i+1の連結成分)\)　であり、

\((i-L_i+1)\cdot(R_i-i)=(頂点 iの連結成分)\cdot(頂点 i+1 の連結成分)\)

が成り立ち、これは UnionFindなどを用いることで \(O(N\alpha(N))\) で処理することができます。

全体の計算量は \(\sum |S_i|=M\) として \(O(M\log(M)+N(\log(N)+\alpha(N)))\) です。

提出 : (80 ms) https://atcoder.jp/contests/abc353/submissions/53394362

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
int main(){
    int n;cin>>n;
    vector<string> s(n);for(auto&e:s)cin>>e;
    sort(s.begin(),s.end());
    vector<pair<int,int>> a;
    for(int i=0;i<n-1;i++){
        int idx=0;
        while(idx<min(s[i].size(),s[i+1].size())&&s[i][idx]==s[i+1][idx])idx++;
        a.push_back({idx,i});
    }
    sort(a.begin(),a.end());reverse(a.begin(),a.end());
    atcoder::dsu d(n);
    long ans=0;
    for(auto[idx,i]:a){
        ans+=long(d.size(i))*d.size(i+1)*idx;
        d.merge(i,i+1);
    }
    cout<<ans<<endl;
}