#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5;
int n, Q;
char s[N];
struct info {
int ans, sum, pre, suf;
} tr[N << 2];
info pushup(info l, info r) {
info u;
u.ans = max({l.pre + r.suf, l.sum + r.ans, r.sum + l.ans});
u.sum = l.sum + r.sum;
u.pre = max(l.pre, l.sum + r.pre);
u.suf = max(r.suf, r.sum + l.suf);
return u;
}
void build(int u = 1, int l = 1, int r = n) {
if (l == r) {
tr[u].sum = s[l];
tr[u].ans = tr[u].pre = tr[u].suf = max<int>(s[l], 0);
return;
}
int mid = (l + r) / 2;
build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
tr[u] = pushup(tr[u * 2], tr[u * 2 + 1]);
}
info query(int ql, int qr, int u = 1, int l = 1, int r = n) {
if (l >= ql && r <= qr) {
return tr[u];
}
int mid = (l + r) / 2;
if (ql > mid) return query(ql, qr, u * 2 + 1, mid + 1, r);
if (qr <= mid) return query(ql, qr, u * 2, l, mid);
return pushup(query(ql, qr, u * 2, l, mid), query(ql, qr, u * 2 + 1, mid + 1, r));
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> s[i];
s[i] = (s[i] == 'T' ? 1 : -1);
}
build();
cin >> Q;
while (Q--) {
int l, r;
cin >> l >> r;
cout << query(l, r).ans << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
34 ms |
5972 KB |
Output is correct |
| 7 |
Correct |
35 ms |
5804 KB |
Output is correct |
| 8 |
Correct |
34 ms |
5900 KB |
Output is correct |
| 9 |
Correct |
28 ms |
5720 KB |
Output is correct |
| 10 |
Correct |
33 ms |
5716 KB |
Output is correct |
| 11 |
Correct |
34 ms |
5896 KB |
Output is correct |
| 12 |
Correct |
33 ms |
5980 KB |
Output is correct |
| 13 |
Correct |
35 ms |
5920 KB |
Output is correct |
| 14 |
Correct |
33 ms |
5976 KB |
Output is correct |
| 15 |
Correct |
33 ms |
5872 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
34 ms |
5972 KB |
Output is correct |
| 7 |
Correct |
35 ms |
5804 KB |
Output is correct |
| 8 |
Correct |
34 ms |
5900 KB |
Output is correct |
| 9 |
Correct |
28 ms |
5720 KB |
Output is correct |
| 10 |
Correct |
33 ms |
5716 KB |
Output is correct |
| 11 |
Correct |
34 ms |
5896 KB |
Output is correct |
| 12 |
Correct |
33 ms |
5980 KB |
Output is correct |
| 13 |
Correct |
35 ms |
5920 KB |
Output is correct |
| 14 |
Correct |
33 ms |
5976 KB |
Output is correct |
| 15 |
Correct |
33 ms |
5872 KB |
Output is correct |
| 16 |
Correct |
311 ms |
27076 KB |
Output is correct |
| 17 |
Correct |
267 ms |
26732 KB |
Output is correct |
| 18 |
Correct |
271 ms |
27032 KB |
Output is correct |
| 19 |
Correct |
230 ms |
26320 KB |
Output is correct |
| 20 |
Correct |
285 ms |
26104 KB |
Output is correct |
| 21 |
Correct |
308 ms |
28232 KB |
Output is correct |
| 22 |
Correct |
299 ms |
27988 KB |
Output is correct |
| 23 |
Correct |
309 ms |
27984 KB |
Output is correct |
| 24 |
Correct |
297 ms |
27748 KB |
Output is correct |
| 25 |
Correct |
292 ms |
27480 KB |
Output is correct |
