atcoder abc140E (计算贡献)

题目链接
大意：让你 ${\sum }_{i=1}^{n-1}{\sum }_{j=i+1}^{n}value(i,j)$∑i=1n−1​∑j=i+1n​value(i,j)，其中 $value(i,j)$value(i,j)为区间第二大的数
思路：考虑每个值的贡献，从大到小扫，我们用两个set维护当前已经扫过的值的位置，然后对于每个值，我们必然是找到最近的大于当前值的两个位置（可能没有），如果有的话，比然是一前一后，然后要满足第二大值的话，必然区间内只能存在当前值，和那两个大于当前值的值当中的一个，那么我们直接讨论一下计算一下区间即可。
细节见代码：

#include<bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()

using namespace std;

LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;}
LL lcm(LL a, LL b) {return a / gcd(a, b) * b;}
LL powmod(LL a, LL b, LL MOD) {LL ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
const int N = 5e5 + 3;
const LL mod = 1e9 + 7;
int n,a[N],pos[N];
set<int>Q,P;
int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],pos[a[i]]=i;
    LL ans=0;
    Q.insert(pos[n]);
    P.insert(-pos[n]);
    for(int i=n-1;i>=1;i--){
        int l=pos[i];
        int L,R,c=1,d=1;
        auto k=Q.lower_bound(l);
        auto x=P.lower_bound(-l);
        if(x!=P.end()){
            L=-(*x)+1;
        }else {L=1;c=-1;}
        if(k!=Q.end()){
            R=*k-1;
        }else {R=n;d=-1;}
        if(k!=Q.end()){
            auto ne=Q.upper_bound(*k);
            int cl,cr;
            if(ne!=Q.end()){
                cr=(*ne)-1;
            }else cr=n;
            ans+=1ll*(cr-*k+1)*i*(pos[i]-L+1);
        }
        if(x!=P.end()){
            auto ne=P.upper_bound(*x);
            int cl,cr;
            if(ne!=P.end()){
                cl=-(*ne)+1;
            }else cl=1;
            ans+=1ll*(-(*x)-cl+1)*i*(R-pos[i]+1);
        }
        Q.insert(pos[i]);
        P.insert(-pos[i]);
    }
    cout<<ans<<endl;
    return 0;
}