提出 #70614577

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int N, A, B;
    string S;
    cin >> N >> A >> B;
    cin >> S;

    // 预处理前缀和数组：pref_a[i]表示前i个字符中'a'的数量，pref_b[i]表示前i个字符中'b'的数量
    vector<int> pref_a(N + 1, 0);
    vector<int> pref_b(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        pref_a[i] = pref_a[i - 1] + (S[i - 1] == 'a' ? 1 : 0);
        pref_b[i] = pref_b[i - 1] + (S[i - 1] == 'b' ? 1 : 0);
    }

    long long ans = 0; // 使用long long防止溢出

    // 遍历每个右端点r
    for (int r = 1; r <= N; r++) {
        // 条件2：子串中'b'的数量 < B → 找到最小左端点l，使得pref_b[l-1] > pref_b[r] - B
        int X = pref_b[r] - B;
        int low_r;
        // 在pref_b[0..r-1]中查找第一个大于X的索引
        auto it_low = upper_bound(pref_b.begin(), pref_b.begin() + r, X);
        if (it_low == pref_b.begin() + r) {
            // 没有找到大于X的值，说明没有满足条件的l
            low_r = r + 1;
        } else {
            int k = it_low - pref_b.begin();
            low_r = k + 1; // l = k + 1
        }

        // 条件1：子串中'a'的数量 ≥ A → 找到最大左端点l，使得pref_a[l-1] ≤ pref_a[r] - A
        int Y = pref_a[r] - A;
        if (Y < 0) {
            // 即使取整个前缀，'a'的数量也不足A，跳过
            continue;
        }
        int high_r;
        // 在pref_a[0..r-1]中查找最后一个小于等于Y的索引
        auto it_high = upper_bound(pref_a.begin(), pref_a.begin() + r, Y);
        if (it_high == pref_a.begin()) {
            // 所有值都大于Y，没有满足条件的l
            high_r = 0;
        } else {
            it_high--; // 退回到最后一个小于等于Y的位置
            int k = it_high - pref_a.begin();
            high_r = k + 1; // l = k + 1
        }

        // 确定有效l的范围：[low_r, high_r]，并确保在[1, r]内
        int left_bound = max(low_r, 1);
        int right_bound = min(high_r, r);
        if (left_bound <= right_bound) {
            ans += (right_bound - left_bound + 1);
        }
    }

    cout << ans << endl;
    return 0;
}

提出情報

ジャッジ結果