RT，昨晚CF的F，因为 $n\le 10^6$，不知道这个最大值分治的复杂度怎样。

线段树找最大值id+启发式双指针统计答案

#pragma comment(linker, "/STACK:102400000,102400000")
#include<iostream>
#include<cstdio>
#include<queue>
#define int long long
using namespace std;
#define N 1050500 
int ans,a[N],n,f[N];
struct node{
	int l,r,id;
}t[N<<2];
#define lc x<<1
#define rc x<<1|1
void build(int x,int l,int r){
	t[x].l=l,t[x].r=r;
	if(l==r){
		t[x].id=l;return ;
	}
	int mid=l+r>>1;
	build(lc,l,mid);build(rc,mid+1,r); 
	if(a[t[lc].id]>a[t[rc].id])t[x].id=t[lc].id;
	else t[x].id=t[rc].id;
}
int find(int x,int l,int r){
	if(t[x].r<l||t[x].l>r)return 0;
	if(l<=t[x].l&&t[x].r<=r)return t[x].id;
	int s=find(lc,l,r),t=find(rc,l,r);
	if(a[s]>a[t])return s;
	return t;
}
void solve(int l,int r){
	if(l>=r)return ;
	int p=find(1,l,r);
	solve(l,p-1);solve(p+1,r);
	int s=ans;
	f[p]=a[p];
	if(p-l<=r-p){
		int j=p;
		for(int i=p-1;i>=l;--i){
			f[i]=min(f[i+1],a[i]);
			while(j<=r&&f[j]>f[i])f[j+1]=min(f[j],a[j+1]),++j;
			ans+=j-p;
		}
	} 
	else {
		int s=ans;
		int j=p;ans+=(r-p+1)*(p-l);
		for(int i=p+1;i<=r;++i){
			f[i]=min(f[i-1],a[i]);
			while(j>=l&&f[j]>f[i])f[j-1]=min(f[j],a[j-1]),--j;
			ans-=p-j-1;
		}
	}
}
void read(int &x){
	x=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}
signed main(){
	ios::sync_with_stdio(false);
	read(n);
	for(int i=1;i<=n;i++)read(a[i]);
	build(1,1,n);
	solve(1,n);
	cout<<ans<<"\n"; 
}

最慢点 764ms