题解 | 山峰数组计数

// 引入C++标准库的所有头文件，竞赛中常用
#include<bits/stdc++.h>
// 使用标准命名空间，避免每次写std::
using namespace std;
// 将int类型重定义为long long，防止数值溢出
#define int long long
// 定义数组的最大长度，2e5+10是竞赛中常见的数组大小设置
const int N=2e5+10;

// 全局变量声明
int n;          // 表示输入的元素个数
int P[N];       // 存储原始输入的数组
int sum[N];     // 前缀和数组，sum[i]表示前i个元素的和

// 核心解题函数
void solve(){
    // 定义三个变量分别存储三个区间的和
    int area1,area2,area3;
    // 存储最终符合条件的方案数
    int res=0;
    
    // 外层循环：枚举第一个分割点i，i最多到n-2（保证后面至少有两个元素）
    for(int i=1,j=2;i<=n-2;i++){
        // 计算三个区间的和：
        // area1: [1, i] 的和（前缀和sum[i]-sum[0]）
        area1=sum[i]-sum[0];
        // area2: [i+1, j] 的和
        area2=sum[j]-sum[i];
        // area3: [j+1, n] 的和
        area3=sum[n]-sum[j];
        
        // 内层循环：移动第二个分割点j，寻找满足条件的最小j
        // 条件：j+1不超过n-1（保证area3至少有一个元素），且area1>=area2 或 area3>=area2
        while(j+1<=n-1&&(area1>=area2||area3>=area2)){
            j++;                // j右移一位
            area2=sum[j]-sum[i];// 更新area2
            area3=sum[n]-sum[j];// 更新area3
        }
        
        // 如果找到满足条件的j（area1 < area2 且 area3 < area2）
        if((area1<area2)&&(area3<area2)){
            // 从j到n-1的所有位置都满足条件，累加方案数
            res+=n-j;
        }
    }
    // 输出最终结果
    cout<<res<<endl;
}

// 主函数，程序入口
signed main(){
    // 关闭同步流，加速cin/cout的输入输出速度（竞赛常用优化）
    ios::sync_with_stdio(false);
    // 解绑cin和cout，进一步加速输出
    cin.tie(0);
    
    // 输入元素个数n
    cin>>n;
    // 输入n个元素，并构建前缀和数组
    for(int i=1;i<=n;i++){
        cin>>P[i];                  // 输入第i个元素
        sum[i]=sum[i-1]+P[i];       // 计算前缀和，sum[i] = sum[0..i]
    }
    
    // 调用解题函数
    solve();

    return 0;
}