题解：AT_abc140_e [ABC140E] Second Sum

George222 · 2024-08-10 18:57:28 · 题解

思路：双向链表+组合数学（不过你要用单调栈也没人拦着你）

我们现在先抛开题面，先换个思路。

我们现在求：这个数能做多少个区间的次大值。

我们现在设 l1, l2, r1, r2 分别为左边第一个比这个数大的 id，第二个比这个数大的 id，右边第一个比这个数大的 id，第二个比这个数大的 id。竟然是次大值，所以我们左边和右边能且仅能包含一个比这个数大的。

我们现在求区间数即为：

• 左边取一个比他大的数的个数 \times 右边取不比他大的数的个数。
• 右边取一个比他大的数的个数 \times 左边取不比他大的数的个数。

即为：

• (l1 - l2) * (r1 - a[i].id)
• (r2 - r1) * (a[i].id - l1)

那么如何获得 l1, l2, r1, r2 呢？

如果我能直接从当前这个数找到这四个数是最好的，就是说像这样的一个链表：

要实现这样我们可以存好 id 后排序，从小到大处理，根据链表的删除机制，到某个数时，一定会成为类似上图的样子。

代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n;
struct Node
{
    ll x;
    ll id;
} a[100005];
ll pre[100005], nxt[100005];
ll ans = 0;
bool cmp(Node a, Node b) {
    return a.x < b.x;
}
void del(ll id)
{
    nxt[pre[id]] = nxt[id];
    pre[nxt[id]] = pre[id];
    return ;
}

int main()
{
    cin >> n;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i].x;
        a[i].id = i;
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[0] = 1;
    pre[n + 1] = n;
    sort(a + 1, a + n + 1, cmp);
    for (ll i = 1; i <= n; i++)
    {
        ll l1, l2, r1, r2;
        // left
        l1 = pre[a[i].id];
        if (l1) l2 = pre[l1];
        else l2 = -1;
        // right
        r1 = nxt[a[i].id];
        if (r1 != n + 1) r2 = nxt[r1];
        else r2 = -1;
        // solve
        if (!(l2 == -1))
            ans += (l1 - l2) * (r1 - a[i].id) * a[i].x;
        if (!(r2 == -1))
            ans += (r2 - r1) * (a[i].id - l1) * a[i].x;
        del(a[i].id);
    }
    cout << ans << "\n";
    return 0;
}