区区区间间间

。

while(j>1&&a[j-1]<=a[i])//下标对应的值等于a[i]的点也能取
    j=l[j-1];

while(j<n&&a[j+1]<a[i])//下标对应的值等于a[i]的点不能取
    j=r[j+1];

Code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int l[100005],r[100005],n,ans;
void solve() {
    for(int i=1;i<=n;++i) {
        int j=i;
        while(j>1&&a[j-1]<=a[i])
            j=l[j-1];
        l[i]=j;
    }
    for(int i=n;i;--i) {
        int j=i;
        while(j<n&&a[j+1]<a[i])
            j=r[j+1];
        r[i]=j;
    }
    for(int i=1;i<=n;++i) {
        ans+=a[i]*(r[i]-l[i]);
        ans+=a[i]*(i-l[i])*(r[i]-i);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--) {
        cin>>n;
        ans=0;
        for(int i=1;i<=n;++i) cin>>a[i];
        solve();
        for(int i=1;i<=n;++i) a[i]=-a[i];
        solve();
        cout<<ans<<endl;
    }
}