Problem
一段序列的映射值为序列的最大值，求一个长度为$n$整数序列$a$的所有本质不同的连续子序列的映射值之和。
Data Range
$1\leq n \leq 2\times10^5$
$1\leq a_i\leq 10^6$
Solution
简化问题
首先考虑一个简化问题：求所有连续子序列的映射值之和。
这个问题比较简单，我们可以从后向前枚举每个位置作为子序列的起始位置，假设当前起始位置为$i$，则$i + 1,i + 2\cdots, n$这些位置作为终止位置对应的子序列的映射值用$mx[x]$表示，$mx[x] = max\{a[i],a[i + 1], \cdots,a[x]\}$。
以$i$作为起始位置时，我们统计答案为 $ans+=\sum_{k = i}^{k = n}mx[k]$。
统计完$i$作为起始位置的全部贡献后，再统计$i - 1$作为起始位置的贡献，这时需要更新所有的$mx[x]$，$mx[x] = max\{mx[x], a[i - 1]\}$，再统计答案。
很显然，以上算法存在两个操作：
- 一个区间$[l,r]$内所有数对$x$取$max$操作
- 求区间$[l,r]$内所有数之和
刚好对应Segment Tree Beats（吉司机线段树）算法，时间复杂度为$O(n\log n)$。
原问题
原问题相较于简化问题，只需要剔除一些重复计算的相同本质的子序列。例如，$[1,2,1,2]$中前两个数构成的序列$[1^{[1]},2^{[2]}]$与后两个数构成的序列$[1^{[3]},2^{[4]}]$是本质相同的序列，在简化问题中会被算两次。
在简化问题中，我们对每个后缀$i$都求出了所有贡献，这其中就会造成重复计算。考虑只有两个后缀$i$、后缀$j$，$i$与$j$的LCP长度为$x$，那么长度为$x$的LCP部分会被重复计算。这让我们联想到后缀数组中有一个$h[i]$数组，$h[i]$数组表示后缀$i$与排名在它前一位的后缀$k$的LCP长度。对于每一个后缀$i$，我们只需要在统计答案时，减去前$h[i]$长度的LCP部分的贡献，即可去重。因为排名在后缀$k$之前的后缀$p$与后缀$i$的LCP长度一定不超过$h[i]$（可以联系后缀数组的相关证明进行理解）。所以每个后缀$i$减去$h[i]$LCP部分后的贡献，都不会与排名在它之前的后缀重复计算，故此时求得的总贡献就是答案。
SA时间复杂度为$O(n\log n)$，Segment Tree Beats 时间复杂度为$O(n\log n)$，总时间复杂度为$O(n\log n)$。
Code
/*************************************************************************
> File Name: 1.cpp
> Author: Knowledge_llz
> Mail: 925538513@qq.com
> Blog: https://www.cnblogs.com/Knowledge-Pig/
> Created Time: 2022/4/5 12:45:18
************************************************************************/
#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
#define ls (node << 1)
#define rs (node << 1 | 1)
const int maxx = 2e5 + 10, inf = 1e9;
int n, m, a[maxx], b[maxx], c[maxx * 10], sa[maxx], x[maxx], y[maxx];
void build_sa(){
for(int i = 1; i <= n; ++i){
x[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
++c[x[i]];
}
for(int i = 1; i <= m; ++i) c[i] += c[i - 1];
for(int i = n; i >= 1; --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 >= 1; --i){ sa[c[x[y[i]]]--] = y[i]; y[i] = 0; }
swap(x, y);
x[sa[1]] = num = 1;
for(int i = 2; i <= n; ++i)
x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? num : ++num;
if(num == n) break;
m = num;
}
}
int rk[maxx], h[maxx];
void get_h(){
for(int i = 1; i <= n; ++i) rk[sa[i]] = i;
int k = 0;
for(int i = 1; i <= n; ++i){
if(rk[i] == 1) continue;
if(k) --k;
int j = sa[rk[i] - 1];
while(j + k <= n && i + k <= n && a[i + k] == a[j + k]) ++k;
h[i] = k;
}
}
LL mn[maxx << 2], se[maxx << 2], cnt[maxx << 2], sum[maxx << 2];
void calc(int node, LL val){
if(val <= mn[node]) return;
sum[node] += (val - mn[node]) * cnt[node];
mn[node] = val;
}
void push_down(int node){
calc(ls, mn[node]);
calc(rs, mn[node]);
}
void push_up(int node){
sum[node] = sum[ls] + sum[rs];
if(mn[ls] < mn[rs]){
mn[node] = mn[ls];
cnt[node] = cnt[ls];
se[node] = min(mn[rs], se[ls]);
}
else if(mn[ls] > mn[rs]){
mn[node] = mn[rs];
cnt[node] = cnt[rs];
se[node] = min(mn[ls], se[rs]);
}
else{
mn[node] = mn[ls];
cnt[node] = cnt[ls] + cnt[rs];
se[node] = min(se[ls], se[rs]);
}
}
void update(int node, int l, int r, int ql, int qr, LL val){
if(val <= mn[node]) return;
if(ql <= l && qr >= r && val < se[node]){
calc(node, val);
return;
}
push_down(node);
int mid = (l + r) >> 1;
if(qr <= mid) update(ls, l, mid, ql, qr, val);
else if(ql > mid) update(rs, mid + 1, r, ql, qr, val);
else{
update(ls, l, mid, ql, mid, val);
update(rs, mid + 1, r, mid + 1, qr, val);
}
push_up(node);
}
LL query(int node, int l, int r, int ql, int qr){
if(ql <= l && qr >= r) return sum[node];
push_down(node);
int mid = (l + r) >> 1;
if(qr <= mid) return query(ls, l, mid, ql, qr);
else if(ql > mid) return query(rs, mid + 1, r, ql, qr);
else return query(ls, l, mid, ql, mid) + query(rs, mid + 1, r, mid + 1, qr);
}
void build(int node, int l, int r){
mn[node] = sum[node] = 0;
se[node] = inf;
cnt[node] = (r - l + 1);
if(l == r) return;
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#endif
int T; cin >> T;
while(T--){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> a[i];
b[i] = a[i];
c[i] = h[i] = 0;
}
sort(b + 1, b + n + 1);
m = n;
build_sa();
get_h();
build(1, 1, n);
LL ans = 0;
for(int i = n; i >= 1; --i){
update(1, 1, n, i, n, a[i]);
ans += sum[1];
if(h[i]) ans -= query(1, 1, n, i, i + h[i] - 1);
}
cout << ans << endl;
}
return 0;
}
