\(\color{purple}\text{The Fox and the Complete Tree Traversal}\)
比较有意思的一题。先考虑一个序列的权值。对长度为 \(len\) 的序列排序，价值为 \(len-1\) ，那么有时候如果后面的元素很大，前面的很小：
3 2 1 300 200 100
我们可以将序列切为 \([1,3]\) ，和 \([4,6]\) 两部分分别排序，相比整个排序，权值减小了一。同时我们发现，序列中的排序区间必然不可能相交，因为相邻都只减少一，相交不如直接整个区间排。
触类旁通，如果我们将序列切成 \(n\) 个区间，满足每个区间中的数都大于所有区间前面的数，那么答案就为 \((len-1)-(n-1)\) 。
我们回到这题，求的是子串序列的权值和。那么易得每出现一组三元组满足 \((l,m,r)\) 满足 \(l\le m< r\) ，且 \(\min[m+1,r]>\max[l,m]\) ，那么就说明在子串 \([l,r]\) 可以在 \(m\) 这个地方切一刀，总答案减一。（总答案的初始值很好求的对吧）。
我的第一想法是枚举 \(l,m\) ， \(r\) 的可选区间显然连续，那么用二分和 \(ST\) 表求出 \(r\) 的最后可选点。复杂度 \(O(n^2)\)
但这显然通过不了。更优的做法是枚举 \(a[i]\) 作为 \(\max[l,m]\) 时，\(l,m\) 就被定下来了，因为\(m\) 前面的数都得小于 \(a[i]\) 而 \(m\) 后面的数都大于 \(a[i]\) ，所以显然 \(m\) 就是 \(a[i]\) 后面第一个大于等于 \(a[i]\) 的数（单调栈），而 \(l\) 更不用说， \([l,i]\) 中的数得小于 \(a[i]\) ，求出 \(l\) 的可选区间，然后 \(r\) 同第一想法一样求出可选区间，复杂度就是 \(O(n)\) 了。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+110;
int read(){
int x=0,f=1;char c=getchar();
while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return x*f;
}
int L[N],R[N],T,n,a[N],st[N][18],lg[N];//2^20>1e6
int query(int l,int r){
return min(st[l][lg[r-l+1]],st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
stack<int>s;
void solve(){
n=read();for(int i=1;i<=n;i++)a[i]=read(),st[i][0]=a[i];
while(!s.empty())s.pop();
for(int i=1;i<=n;i++){
while(!s.empty() && a[s.top()]<a[i])s.pop();
if(s.empty())L[i]=0;
else L[i]=s.top();
s.push(i);
}
while(!s.empty())s.pop();
for(int i=n;i>=1;i--){
while(!s.empty() && a[s.top()]<a[i])s.pop();
if(s.empty())R[i]=n+1;
else R[i]=s.top();
s.push(i);
}
lg[1]=0;for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;
for(int i=1;i<=17;i++)
for(int j=1;j<=n;j++)
st[j][i]=min(st[j][i-1],st[j+(1<<i-1)][i-1]);
int sum=0;
for(int l2=1;l2<=n;l2++){
int l1=L[l2]+1;
int r1=R[l2];if(r1>n)continue;
int l=r1,r=n,r2=-1;
while(l<=r){
int mid=(l+r)>>1;
if(query(r1,mid)>=a[l2]){
r2=mid;
l=mid+1;
}
else r=mid-1;
}
sum+=(l2-l1+1)*(r2-r1+1);
}
int assist=0;
for(int i=1;i<n;i++)assist+=i*(n-i);
printf("%lld\n",assist-sum);
return ;
}
signed main(){
T=read();while(T--)solve();
return 0;
}