cf 2121F. Yamakasi 解题

题目

给定数组 \(a\) 和整数 \(s, x\)，求有多少子数组满足：

1. 子数组和 = \(s\)
2. 子数组最大值 = \(x\)

思路

• 最大值 = \(x\) ⇒ 子数组必须包含至少一个 \(x\)，且不能包含 \(> x\) 的数。
• 用 \(> x\) 的元素分割数组，在每个连续段（所有元素 ≤ x）内处理。
• 遍历时维护左指针 \(l\) 和哈希表 \(mp\)（存储可能成为左端点的前缀和）。
• 遇到 \(a[i] == x\) 时，将 \([l, i-1]\) 的前缀和加入 \(mp\)，更新 \(l = i\)。
• 每次查询 \(mp[sum[i] - s]\) 累加到答案。

代码

#include <bits/stdc++.h>
using ll = long long;
using namespace std;
const int N = 1e7 + 5;
ll n, s, x;
void solve() {cin >> n >> s >> x;vector<ll> a(n + 1), sum(n + 1, 0);map<ll, ll> mp;for (int i = 1; i <= n; i++)cin >> a[i], sum[i] = sum[i - 1] + a[i];ll l = 0, ans = 0;for (int i = 1; i <= n; i++) {if (a[i] > x) {//更新mpmp.clear();l = i;} else {//a[i]<=xif (a[i] == x) {//符合条件就添加while (l < i) {mp[sum[l]]++;l++;}}ans += mp[sum[i] - s];//a[i]<=x 前面有x了就加进去}}cout << ans << '\n';
}
int main() {int t = 1;cin >> t;while (t--) {solve();}return 0;
}