[ABC140] E.Second Sum

发表于 | 更新于 | 分类于 ，
本文字数： 10k

链接

\(\text{ABC140 E - Second Sum}\)

题意

  给你一个长度为\(n\)的序列\(P\)，对于一个区间\((L,R)\)，\(X_{L}\)为该区间第二大的数，求出\(\displaystyle\sum_{L=1}^{N-1}\sum_{R-L+1}^{N}X_{L,R}\).

  即让你求出对于每一个\(a[i]\)，\(a[i]\)作为第二大值的区间个数\(cnt\)乘以\(a[i]\)，求出这个结果。

  输入格式：第一行输入\(N\)，第二行输入一个长度为\(n\)的序列\(P\).

  输出格式：输出一行.

  数据范围：\(2\leq n\leq 10^{5},1\leq P_{I}\leq n,P_{i}\neq P_{j}\).

分析

  首先整个序列是\(1-n\)的一个排列，首先考虑这样一种情况，对于\(a[i]\)来说，\(a[x_1]、a[x_2]\)分别是比\(a[i]\)第一大、第二大的并且位于\(a[i]\)的两个数，\(a[x_3]、a[x_4]\)则是比\(a[i]\)第一大、第二大位于\(a[i]\)右边的两个数，那么则有\(a[i]\)作为第二大的数对答案的贡献为：\(((x_2-x_1)*(x_3-i)+(x_4-x_3)*(i-x_2))*a[i]\)。

  所以实际上我们只关心，比当前\(a[x]\)大的数，以及它的下标；那么我们使用一个\(set\)，将数列从大到小，将它们的下标插入\(set\)里，对当前的\(a[i]\)，在\(set\)里对\(i\)进行二分找\(x_1、x_2、x_3、x_4\)，此时\(set\)里的元素一定是比\(a[i]\)大的，这样就能以上面的方式求出\(a[i]\)对答案的贡献。

  注意考虑特殊的情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<iostream>
#include<string>
#include<queue>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

#define mod 998244353
#define inf 0x7f7f7f7f
#define maxn 500005
#define N 300005
typedef long long ll;

inline int read()
{
    int x = 0;
    int f = 1;
    char c = getchar();
    while (c<'0' || c>'9')
    {    
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0'&&c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x*f;
}

int n, a[N], p[N];
typedef multiset<int>::iterator st;
int main() {
    cin >> n;
    multiset<int> s;
    s.insert(0), s.insert(0);
    s.insert(n + 1), s.insert(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[a[i]] = i;
    }
    ll ans = 0;
    for (int i = n; i >= 1; i--) {
        st r2 = s.upper_bound(p[i]), l2 = r2++;
        st r1 = l2--, l1 = l2--;
        ans += 1ll * (*l1 - *l2) * (*r1 - p[i]) * i;
        ans += 1ll * (*r2 - *r1) * (p[i] - *l1) * i;
        s.insert(p[i]);
    }
    cout << ans << endl;
}