Day15 T6 参考

· 2026-7-25 15:31:06
#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n = 0;
    int m = 0;
    if (!(cin >> n >> m)) {
        return;
    }

    string s;
    cin >> s;

    // 1. 计算前缀和数组 p (1-indexed)
    vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        p[i] = p[i - 1] + (s[i - 1] == '+' ? 1 : -1);
    }

    // 2. 预处理前缀的最值
    vector<int> pref_max(n + 1, 0);
    vector<int> pref_min(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        pref_max[i] = std::max(pref_max[i - 1], p[i]);
        pref_min[i] = std::min(pref_min[i - 1], p[i]);
    }

    // 3. 预处理后缀的最值 (从后往前动态规划)
    vector<int> suf_max(n + 2, 0);
    vector<int> suf_min(n + 2, 0);
    suf_max[n] = p[n];
    suf_min[n] = p[n];

    for (int i = n - 1; i >= 1; --i) {
        suf_max[i] = std::max(suf_max[i + 1], p[i]);
        suf_min[i] = std::min(suf_min[i + 1], p[i]);
    }

    // 4. 回答 m 次询问
    for (int i = 0; i < m; ++i) {
        int l = 0;
        int r = 0;
        cin >> l >> r;

        // 第一阶段(前缀 [0, l-1])的最值
        int cur_max = pref_max[l - 1];
        int cur_min = pref_min[l - 1];

        // 第二阶段(后缀 [r+1, n])的最值合并
        if (r < n) {
            const int shift = p[l - 1] - p[r];
            cur_max = std::max(cur_max, suf_max[r + 1] + shift);
            cur_min = std::min(cur_min, suf_min[r + 1] + shift);
        }

        // 不同值的个数 = 最大值 - 最小值 + 1
        cout << (cur_max - cur_min + 1) << "\n";
    }
}

int main() {
    // 开启 I/O 加速
    cin.tie(nullptr)->sync_with_stdio(false);

    int t = 0;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }

    return 0;
}
2 次查看 举报

0 条评论

目前还没有评论...

Be the first to comment!

返回讨论列表
root
2678
通过题目
18
发帖数