cf | Median Splits

题目：

总结一下主要逻辑：

1. 映射：

   • 把数组元素变成 1 或 -1。
   • 1 表示「好元素」（小于等于 k），-1 表示「坏元素」。

2. 前缀和：构建前缀和数组，方便快速计算子段的「好元素数量 - 坏元素数量」。

3. 找位置分割：

   • 维护一个最小前缀和的位置 pos。
   • 当前 i 时，判断：
     • 从 pos+1 到 i 这段区间，好元素数量 ≥ 坏元素数量（即子段和非负）。
     • 或者，从 i+1 到 n 的区间，好元素数量 ≥ 坏元素数量。

4. 反转数组再做一遍：因为可以 l、r 不一定是左边小、右边大，所以反过来做一次，避免漏掉情况。

5. 输出结果：有符合条件的分割就输出 YES，否则输出 NO。

额外小贴士：

• 为什么把 <=k 的映射成 1？

  因为要求的是三个子段的中位数 ≤ k，如果子段里面好元素数量 ≥ 坏元素数量，那么中位数更容易是小的数。

• 为什么要反转？

  因为分 l 和 r 的位置可以不固定，反转保证左右两边都能正确判断。

代码：

无注释版：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],s[N];
void solve(){int n,k;cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];if(a[i]<=k) a[i]=1;else a[i]=-1;}for(int op=1;op<=2;op++){reverse(a+1,a+n+1);for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}int pos=-1;for(int i=1;i<n;i++){if(pos>=0)if(s[i]-s[pos]>=0||s[n]-s[i]>=0) {cout<<"YES\n";return;}if(s[i]>=0){if(pos==-1||s[i]<s[pos]) pos=i;}}}cout<<"NO\n";
}
int main(){int t;cin>>t;while(t--){solve();}
}

有注释版：

#include<bits/stdc++.h> // 包含所有标准库
using namespace std;const int N=2e5+10; // 定义最大数组大小（保证足够大）
int a[N],s[N]; // a[] 是原数组，s[] 是前缀和数组// 单组数据处理
void solve(){int n,k;cin>>n>>k; // 读入数组长度 n 和目标值 k// 读入数组元素，同时进行映射for(int i=1;i<=n;i++){cin>>a[i];if(a[i]<=k) a[i]=1; // 小于等于 k 的元素映射为 1（好元素）else a[i]=-1;       // 大于 k 的元素映射为 -1（坏元素）}// 做两遍：原数组一遍、翻转数组一遍for(int op=1;op<=2;op++){reverse(a+1,a+n+1); // 将 a[1] 到 a[n] 整个数组翻转// 计算前缀和 s[i]，s[0]=0for(int i=1;i<=n;i++){s[i]=s[i-1]+a[i];}int pos=-1; // 初始化一个位置，记录当前最小的前缀和下标// 枚举 l 位置for(int i=1;i<n;i++){ // 注意 i 只到 n-1，因为 r < nif(pos>=0){// 如果之前存在 pos，并且 [pos+1, i] 这段区间的和 >=0// 或者 [i+1, n] 这段区间的和 >=0if(s[i]-s[pos]>=0 || s[n]-s[i]>=0) {cout<<"YES\n"; // 找到了符合条件的分割，输出 YESreturn;}}// 更新 pos：找一个前缀和最小的位置（用于维护 s[i]-s[pos]）if(s[i]>=0){if(pos==-1 || s[i]<s[pos]) pos=i;}}}// 如果遍历完两遍还没找到符合条件的分割cout<<"NO\n";
}int main(){int t;cin>>t; // 读入组数while(t--){solve(); // 每组数据调用 solve 处理}
}