题解：CF2121F Yamakasi

postpone · 2025-06-21 01:51:18 · 题解

一个非常经典的模型：长为 n 的序列，有多少个子段满足和为 s？

我们转化一下，做个前缀和，现在求有多少组 (l, r) 满足 pre_r - pre_{l-1} = s。再转换一下，对于每个位置 r，求它之前之前有多少个 i 满足 pre_{i-1}=pre_r-s。

那么维护 pre_i 值到数量的映射，从前到后扫过去就行了。

auto work = [&]() {
    map<i64, int> f;
    f[0]++;

    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        if (f.contains(pre[i + 1] - s)) {
            ans += f[pre[i + 1] - s];
        }
        f[pre[i + 1]]++;
    }
    return ans;
};

这道题多了一个限定，不仅要和为 s，还要最大值为 x。

要求最大值正好等于 x，不是很好搞。我们再转化一下，先求所有最大值不大于 x 的，再求所有不大于 x-1 的，把两者相减即为答案。

void solve() {
    int n, x;
    i64 s;
    cin >> n >> s >> x;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<i64> pre(n + 1);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + a[i];
    }

    auto work = [&](int x) {
        map<i64, int> f;
        f[0]++;

        i64 ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > x) { // 如果大于 x，就把之前的扔掉重新开始计数
                f.clear();
            }
            if (f.contains(pre[i + 1] - s)) {
                ans += f[pre[i + 1] - s];
            }
            f[pre[i + 1]]++;
        }
        return ans;
    };

    cout << work(x) - work(x - 1) << "\n";
}