题目大意

题意

数据范围

​

分析

考虑 pip_i 作为答案的贡献

易想到 找到 pip_i 左右两边两个大于 pip_i 的数，分别记录其位置为 l,L,r,Rl,L,r,R

那么对答案 resres 的贡献为

res+=(l−L)∗(r−pos[pi])∗pires += (l-L) * (r-pos[p_i])*p_i

res+=(R−r)∗(pos[pi]−l)∗pires += (R-r) * (pos[p_i]-l)*p_i

分析

现在考虑如何找到 pip_i 左右两边大于其的 22 个

可以考虑 setset

然后从大到小枚举数，把其位置 pospos 插入 setset 中

这样可以保证对于 pip_i 在 setset 中的位置上的值都是大于它的

移动迭代器即可快速找到

时间复杂度 O(nlogn)O(nlogn)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int pos[100005];
signed main()
{
    int n;cin >>n;
    vector<int> a(n+1);
    
    for(int i = 1;i <= n;i++) cin >> a[i],pos[a[i]] = i;

    set<int> s;
    s.insert(0);s.insert(n+1);
    int res = 0;
    for(int i = n;i>=1;i--){
        s.insert(pos[i]);
        auto it = s.lower_bound(pos[i]);
        auto l = it,r = it; l--,r++;
        auto L = l,R = r;L--,R++;
        if(*l>=1) res += i*(*l-*L)*(*r-pos[i]);
        if(*r<=n) res += i*(*R-*r)*(pos[i]-*l);
    }
    cout << res << endl;
    return 0;
}