一道数数题，看了很多讲解才看明白，后来上手写的时候发现了 $O(n)$ 的做法。

F. We Be Summing

题意

确定子数组中有多少好区间，好区间的定义是可将数组分成两部分（两部分都不能为空），保证前半截最小值 $x$ 和后半截最大值 $y$ 相加能得到 $k$ 。

思路

首先每个合法区间肯定存在左边的最小值和右边的最大值，所以这类题目我们转而求某个最小值所对应的合法区间种类数即可。

我们最简单的思路就是考虑枚举每个 $x$ ，先确定这个 $x$ 能使用的左端点个数，然后再找对应的合法右端点个数，然后相乘就可以。

我们可以先预处理出来计算每个数的 “min管辖区间” ，也就是它能在哪些区间内成为最小值（包括向前和向后），这里我们注意 $x$ 往前拓展遇到相同的数就需要停止，为了防止待会计算有效左端点个数*有效右端点个数 出现重复计算的问题，但是往后拓展遇到相同的数不可以停止。然后还需要预处理 “max管辖区间” ，也就是当前这个数能在那些区间成为最大值（这里也包括向前和向后），这里 $y$ 向前拓展遇到相同的数不需要停止，但是向后拓展遇到相同的数就需要停止，同样也是为了防止重复计算。

然后我们枚举 $x$ 的时候，看某个 $y$ 能否产生贡献即判断 $x$ 的“min管辖区间”右端点能否和 $y$ 的“max管辖区间”产生交汇，如果可以那就说明这个 $y$ 可以产生贡献。

注意到 $y$ 的 “max管辖区间”左端点一定是不减的，固定 $x$ 后，“min管辖区间”右端点就固定了，可以二分快速求出有效的 $y$ 的个数（这些有效的 $y$ 一定是连续的），但是这些 $y$ 还需要在当前的 $x$ 后面，这时候我们还能注意到，随着 $x$ 往后枚举，“min管辖区间”右端点也在不断增大，有效 $y$ 的区间也在不断后退，所以可以使用双指针解决。

样例解释

$$ \begin{aligned} &6 \ 8 \\ &\textcolor{red}{4} \ 5 \ \textcolor{blue}{4} \ 5 \ \textcolor{green}{4} \ 5 \end{aligned} $$

以下样例解释均使用开区间，方便后续计算

这个红色4作为 $x$ 的 “min管辖区间” 即为 $(0,7)$ ，蓝色4作为 $y$ 的 “max管辖范围是” $(2,4)$ ，绿色4作为 $y$ 的 “max管辖范围是” $(4,6)$，所以蓝色4绿色4均可和红色四组队，对答案贡献为 $1(红色4贡献的有效左端点个数)\times 2(蓝色绿色4贡献的右端点个数)=2$

这个蓝色4作为 $x$ 的 “min管辖区间” 即为 $(1,7)$ ，绿色4作为 $y$ 的 “max管辖范围是” $(4,6)$，所以蓝色4可和绿色四组队，对答案贡献为 $2(蓝色4贡献的有效左端点个数)\times 1(绿色4贡献的右端点个数)=2$

故本组样例答案为4。

代码

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(x) 42
#endif

#define int long long
void solve() {
    int n,k;cin>>n>>k;
    vector<int> a(n+2);

    vector<vector<int>> pos(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]].push_back(i);
    }
    
    //L0记录i作为最小值的区间左端点，R0记录作为最小值右端点（均为开区间）
    //L1记录i作为最大值的区间左端点，R1记录作为最大值右端点（均为开区间）
    //L0 R1并不会用到具体位置，只关心有几个有效点，所以直接改为存储有效点个数
    vector<int> L0(n+1),L1(n+1),R0(n+1),R1(n+1);
    vector<int> st;
    st.push_back(0);
    a[0]=0;
    //min向前延申
    for(int i=1;i<=n;i++){
        while(st.size()&&a[st.back()]>a[i])st.pop_back();
        L0[i]=i-st.back();
        st.push_back(i);
    }
    //min向后延申
    st.clear();
    st.push_back(n+1);
    a[n+1]=0;
    for(int i=n;i>=1;i--){
        while(st.size()&&a[st.back()]>=a[i])st.pop_back();
        R0[i]=st.back();
        st.push_back(i);
    }
    //max向前延申
    st.clear();
    st.push_back(0);
    a[0]=1e18;
    for(int i=1;i<=n;i++){
        while(st.size()&&a[st.back()]<=a[i])st.pop_back();
        L1[i]=st.back();
        st.push_back(i);
    }
    //max向后延申
    st.clear();
    st.push_back(n+1);
    a[n+1]=1e18;
    for(int i=n;i>=1;i--){
        while(st.size()&&a[st.back()]<a[i])st.pop_back();
        R1[i]=st.back()-i;
        st.push_back(i);
    }
    int ans=0;
    for(int x=1;x<=n;x++){
        int y=k-x;
        if(y<1||y>n)continue;
        vector<int>l0(1),r0(1),l1(1),r1(1);
        vector<int> pre(1);
        int cntx=pos[x].size(),cnty=pos[y].size();
        vector<int> X(1),Y(1);

        for(auto px:pos[x]){
            l0.push_back(L0[px]);
            r0.push_back(R0[px]);
            X.push_back(px);
        }
        for(auto py:pos[y]){
            l1.push_back(L1[py]);
            r1.push_back(R1[py]);
            pre.push_back(pre.back()+r1.back());
            Y.push_back(py);
        }
        int l=0,r=0;
        for(int i=1;i<=cntx;i++){
            while(l<cnty&&Y[l+1]<=X[i])l++;
            while(r<cnty&&l1[r+1]<r0[i])r++;
            ans+=l0[i]*(pre[r]-pre[l]);
        }
    }
    cout<<ans<<'\n';

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin>>T;
    while(T--)solve();
    return 0;
}

参考资料

Codeforces Round 1005 (Div. 2)（A-F）讲解

Codeforces Round 1005（Div.2）晚开打了，但是 1.5h AK rk27！OI 比赛实况第四十二期。