Atcoder Beginner Contest 140E（多重集，思维）

#define HAVE_STRUCT_TIMESPEC
#include<bits/stdc++.h>
using namespace std;
multiset<long long>mst;
long long a[100007];
int main(){
long long n;
cin>>n;
long long x;
for(long long i=0;i<n;++i){
cin>>x;
a[x]=i;
}
mst.insert(-1);
mst.insert(-1);
mst.insert(n);
mst.insert(n);
long long ans=0;
set<long long>::iterator pos,nex,pre,pree;
for(long long i=n;i;--i){//倒着插，使得集合内除了初始插入的两个-1和两个n其余的位置它们的值都比后插入的值大
pos=mst.upper_bound(a[i]);//比当前i的值大的下一个值的位置
nex=next(pos);//比pos大的下一个值的位置
pre=prev(pos);//比当前i的值小的上一个值的位置
pree=prev(pre);//比pre小的上一个值的位置
ans+=i*((*nex-*pos)*(a[i]-*pre)+(*pos-a[i])*(*pre-*pree));//区间内只有一个值比当前i值大
mst.insert(a[i]);//将当前值的位置插入
}
cout<<ans;
return 0;
}

巴特西

Atcoder Beginner Contest 140E（多重集，思维）

最新文章

热门文章