题解：AT_abc140_e [ABC140E] Second Sum

TH911 · 2024-11-16 20:18:51 · 题解

声明：这并不是一篇算法独特的题解，相关方法此篇题解已有，但绝对更为详细。

广告：个人Blog同步链接。

题意分析

当 a_i 对答案产生贡献时，当且仅当存在区间 [l,r] 满足 i\in[l,r] 且 a_i 是 [l,r] 的次大值。

由此我们开始做题。

计算合法区间数

显然，当且仅当区间中有且仅有一个数大于 a_i 时，答案会增加 a_i。

那么我们考虑算出，对于每一个 a_i，会造成多少个 a_i 的贡献。

如果我们找出了 a_i 左右两边第一个、第二个大于 a_i 的数，从左至右分别记作 a_{dl_i},a_{l_i},a_{r_i},a_{dr_i}（满足 dl_i<l_i<i<r_i<dr_i 且 a_{dl_i},a_{l_i},a_{r_i},a_{dr_i}>a_i），那么这四个数中肯定只能有一个和 a_i 处于同一个区间（否则 a_i 不为次大值）。

那么我们所需要的会对答案造成贡献的区间就不会包含 a_{dl_i} 和 a_{dr_i}（因为一旦包含 a_{dl_i}，就一定会包含 d_{l_i}，r_i,dr_i 同理）。

既然如此，令合法区间为 [L,R]，合法情况就只有两种：

图示：

当 L\in[dl_i+1,l_i],R\in[i,r_i-1] 时，则合法区间数为 \left(l_i-\left(dl_i+1\right)+1\right)\left(\left(r_i-1\right)-i+1\right)=(l_i-dl_i)(r_i-i)。

同样地，当 L\in[l_i+1,i],R\in[r_i,dr_i-1] 时，合法区间数为 \left(i-l_i\right)\left(dr_i-r_i\right)。

那么 a_i 对答案的总贡献就是 a_i\times\left[\left(l_i-dl_i\right)\left(r_i-i\right)+\left(i-l_i\right)\left(dr_i-r_i\right)\right]，可以 \mathcal O\left(1\right) 求解。

则最终答案为 \large \sum\limits_{i=1}^n{a_i\times\left[\left(l_i-dl_i\right)\left(r_i-i\right)+\left(i-l_i\right)\left(dr_i-r_i\right)\right]}（下标从 1 开始）。

但这时我们需要注意的是，这四个数都有可能不会存在，那么初值就变得十分重要，甚至会影响最终答案的正确性。当然，你不嫌麻烦你特判也行。

• 如果你的下标从 1 开始：

  for(int i=1;i<=n;i++){
    l[i]=dl[i]=0;
    r[i]=dr[i]=n+1;
  }

• 如果你的下标从 0 开始：

  for(int i=0;i<n;i++){
    l[i]=dl[i]=-1;
    r[i]=dr[i]=n;
  }

（其实就是类似于“值域两端”）

解释一下为什么：（下标从 1 开始，从 0 开始和从 1 开始差不多，不能理解可以手推或参见上图）

以 l_i,dl_i 为例，r_i,dr_i 同理可得。

首先，l_i=dl_i=0 的好处就是选取区间时 l_i+1=dl_i+1=1（不存在的话）。

如果 l_i 不存在，那么 dl_i 绝对不存在：l_i=dl_i=1,l_i-dl_i=0，上文中 [L_1,R_1] 的区间因为要选取 l_i 自然不存在，正确；对于 [L_2,R_2]，已经在右边选取了 r_i，l_i 自然不会选取到，不影响答案。

如果 l_i 存在，dl_i 不存在：[L_1,R_1] 选取了 l_i，则 1\sim l_i 都可以选取，此时 l_i-dl_i=l_i-0=l_i，正确；对于 [L_2,R_2]，同样与 l_i,dl_i 无关，不影响答案。

这样，我们便可以 \mathcal O\left(n\right) 求出最终答案。

如何计算四个数的位置

如果你不知道 set

说了这么多，我们还是不知道如何求出 dl_i,l_i,r_i,dr_i。

事实上，我们仅仅需要从大至小向 set 中加入 a_i，然后利用前驱、后继节点来判断大小关系即可。

令 p_i 表示 a_i 的下标，那么按照 a_i 值排序，使得 \large a_{p_1}>a_{p_2}>a_{p_3}>\cdots>a_{p_n}。

这时我们用 i 遍历 [1,n]，每次在 set 中执行 lower_bound(p[i])（或者 upper_bound(p[i]) 也行，因为 p_i 不重复），找到第一个大于 p_i 的下标 p_x。

那么 p_x 在 p_i 之前插入 set，代表 a_{p_x}>a_{p_i}，又有 p_x>p_i 且 p_x 最小，则 p_x=r_{p_i}。

而 dr_{p_i} 也很简单，当 p_x 不为 set 的最后一个元素（不然越界）时，找到 p_x 的后继节点即可。由 set 的有序特性且 p_i 不重复，p_x 的后继节点就是最小的大于 p_x 的元素 p_{x'}，dr_{p_i}=p_{x'}。

对于 l_{p_i}，其实就是 p_{x} 的前驱节点 p_y。因为 set 内 p_i 不重复、p_x 最小且 p_y<p_x,p_x>p_i，有 p_y<p_i 且 p_y 最大。

那么就有 l_{p_i}=p_y。和 dr_{p_i} 同理，dl_{p_i} 为 p_y 的前驱节点 p_{y'}。

注意判定越界。

最后记得将 p_i 插入 set 即可。

不会有人不会算前驱后继节点吧。

使用 next() 和 prev() 即可。

虽然说对迭代器进行自减运算、自加运算，或者进行数学运算后强制类型转换也行，但是确实没有这两个简单。

注意事项

• 开 long long。

AC代码

//#include<bits/stdc++.h>
#include<algorithm> 
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<set> 
using namespace std;
typedef long long ll;
const int N=2e5;
ll n,a[N+1],p[N+1],l[N+1],dl[N+1],r[N+1],dr[N+1];
bool cmp(ll x,ll y){
    if(a[x]!=a[y])return a[x]>a[y];
    return x<y;
}
int main(){
    /*freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);*/

    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",a+i);
    for(ll i=1;i<=n;i++){
        p[i]=i;
        l[i]=dl[i]=0;
        r[i]=dr[i]=n+1;
    }sort(p+1,p+n+1,cmp);
    set<ll>s;
    for(ll i=1;i<=n;i++){
        auto pl=s.lower_bound(p[i]);
        if(pl!=s.end()){
            r[p[i]]=*pl;
            if(next(pl)!=s.end())dr[p[i]]=*next(pl);
        }if(pl!=s.begin()){
            pl--;
            l[p[i]]=*pl;
            if(pl!=s.begin())dl[p[i]]=*prev(pl);
        }s.insert(p[i]);
    }ll ans=0;
    for(ll i=1;i<=n;i++)ans+=a[i]*((l[i]-dl[i])*(r[i]-i)+(i-l[i])*(dr[i]-r[i]));
    printf("%lld\n",ans);

    /*fclose(stdin);
    fclose(stdout);*/
    return 0;
}