欢迎来到起遇信息学
起遇信息学正处于上线筹建阶段,以下功能已全部开放免费体验: ✅ 完整题库浏览与代码提交评测(C / C++ / Python / Java 等) ✅ 入门到进阶的系列课程试读、作业与考试 ✅ AI 提示、AI 作业分析等智能助教功能 ✅ 赛事模拟与个人能力报告 ✅ 邮箱注册开放 ⏳ 付费课程订阅与微信/支付宝支付通道 ⏳ 手机号登录,微信扫码登录、微信公众号绑定 使用中如遇任何问题,欢迎通过页面底部 **"联系我们"** 与我们沟通。
#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;
}
0 条评论
目前还没有评论...
Be the first to comment!
返回讨论列表
2678
通过题目
18
发帖数