点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod=998244353;
const int N=1e6+7;
void solve(){
int n;cin>>n;
vector<int>p(n);
for(int i=0;i<n;i++) cin>>p[i];
//左最小值,右最大值,左最大值,右最小值
vector<int>lmin(n,-1),rmax(n,n),lmax(n,-1),rmin(n,n);
vector<int>smin,smax; //最小栈,最大栈
for(int i=0;i<n;i++){
while(!smin.empty()&&p[i]<p[smin.back()]){
rmin[smin.back()]=i;
smin.pop_back();
}
if(!smin.empty()) lmin[i]=smin.back();
smin.push_back(i);
while(!smax.empty()&&p[i]>p[smax.back()]){
rmax[smax.back()]=i;
smax.pop_back();
}
if(!smax.empty()) lmax[i]=smax.back();
smax.push_back(i);
}
ll ans=0;
for(int i=0;i<n;i++) cout<<lmin[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++) cout<<rmin[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++) cout<<lmax[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++) cout<<rmax[i]<<" ";
cout<<"\n";
for(int i=0;i<n;i++){ //计算的是以 i 为最大值下标的合法结果数
int L=lmax[i],R=rmax[i];
//if只是用来加速，里面的计算本质上的是一样的
if(R-i<i-L){ //右边短，搜右边
int now=n; //左最小值下标，当前区间右端点是j
for(int j=i;j<R;j++){
now=min(now,lmin[j]);
cout<<i<<" 1"<<'\n';
ans+=max(0,now-L); //区间左端点包含左最小值,不包含左最大值
}
} else { //搜左边
int now=i; //最小值下标，当前区间左端点是j
for(int j=i;j>L;j--){
if(p[j]<p[now]) now=j;
cout<<i<<" 2"<<"\n";
if(now!=i){ //最小值下标不能是i,因为i是最大值下标
cout<<min(rmin[now],R)<<" dsa\n";
ans+=max(0,min(rmin[now],R)-i); //区间右端点不包含右最小值和右最大值
cout<<ans<<"\n";
}
}
}
// cout<<ans<<"\n";
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
solve();
}
/*
6
3 1 5 4 2 7
-1 -1 1 1 1 4
1 6 3 4 6 6
-1 0 -1 2 3 -1
2 2 5 5 5 6
0 2
1 2
2 2
2 2
5 dsa
3
2 2
5 dsa
6
3 2
4 2
5 1
11
*/
