CF2064F We Be Summing 题解

Zskioaert1106 · 2026-11-10 16:40:00 · 题解

题目传送门：CF2064F We Be Summing

题意简述

求数组 a_1 \sim a_n 有多少子数组可以划分为两段非空前后缀，满足前缀 \min 加后缀 \max 等于 k。

题目分析

首先单调栈处理出每个 i 作为 \min 和 \max 的管辖范围，分别记为 [l_i,r_i] 和 [L_i,R_i]。

考虑枚举每个位置作为前缀 \min 的方案数。显然向前的部分是简单的，即 i-l_i+1 种左端点。考虑向后的部分，需要存在分割使得后缀 \max 恰好为 k-a_i，即：k-a_i \leqslant n、存在等于 k-a_i 的点、不存在大于 k-a_i 的点。

建议画个图感受一下。结论是：在第一个 r_i 以外的大于 k-a_i 的元素之前的、所有 a_j=k-a_i 的 [j,R_j] 之并。

前者扫描线 + 树状数组，后者扫描线 + 差分。

（你我令 i 是 [l_i,r_i] 中第一个 \min，也是 [L_i,R_i] 中最后一个 \max，注意到管辖区间不交，因此并即长度和。）

代码实现

#include<bits/stdc++.h>
using namespace std;
constexpr int N=200005;
int T,n,k,a[N],l[N],r[N],R[N],d[N],to[N],cnt[N],tmp[N];
vector<int>v[N];
long long ans;
int query(int x){
    int s=n+1;
    for(int i=n+1-x;i;i-=i&-i)s=min(s,d[i]);
    return s;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>k,ans=0;
        for(int i=1;i<=n;i++)cin>>a[i];
        stack<int>t;
        for(int i=n;i;t.push(i--))
            while(!t.empty()&&a[i]<=a[t.top()])l[t.top()]=i,t.pop();
        while(!t.empty())l[t.top()]=0,t.pop();
        for(int i=1;i<=n;t.push(i++))
            while(!t.empty()&&a[i]<a[t.top()])r[t.top()]=i,t.pop();
        while(!t.empty())r[t.top()]=n+1,t.pop();
        for(int i=1;i<=n;t.push(i++))
            while(!t.empty()&&a[i]>=a[t.top()])R[t.top()]=i,t.pop();
        while(!t.empty())R[t.top()]=n+1,t.pop();
        for(int i=1;i<=n;i++){
            if(k-a[i]>n);
            else if(r[i]>n)to[i]=n+1;
            else v[r[i]].push_back(i);
        }
        fill(d+1,d+1+n,n+1);
        for(int i=n;i;i--){
            for(int j=n+1-a[i];j<=n;j+=j&-j)d[j]=i;
            for(int j:v[i])to[j]=query(k-a[j]+1);
        }
        for(int i=1;i<=n;i++)v[i].clear();
        for(int i=1;i<=n;i++){
            if(k-a[i]>n||to[i]>n);
            else v[to[i]].push_back(i);
        }
        fill(cnt+1,cnt+1+n,0);
        fill(tmp+1,tmp+1+n,0);
        for(int i=n;i;i--){
            if(k-a[i]<=n)ans+=(long long)(i-l[i])*(tmp[i]+=cnt[k-a[i]]);
            cnt[a[i]]+=R[i]-i;
            for(int j:v[i])tmp[j]-=cnt[k-a[j]];
        }
        for(int i=1;i<=n;i++)v[i].clear();
        cout<<ans<<'\n';
    }
    return 0;
}

AC 记录。