#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string s;
const int mxN = 2e6+10;
array<int, 4> st[mxN];
array<int, 4> comb(array<int, 4> a, array<int, 4> b) {
array<int, 4> ans;
ans[0] = a[0] + b[0];
ans[1] = max(a[1], a[0] + b[1]);
ans[2] = max(b[2], b[0] + a[2]);
ans[3] = max({a[0]+b[3], a[3]+b[0], a[1]+b[2]});
return ans;
}
void build(int node, int l, int r) {
if(l == r) {
if(s[l] == 'T') st[node] = {1, 1, 1, 1};
else st[node] = {-1, 0, 0, 0};
return ;
}
int mid = (l+r)/2;
build(node*2, l, mid);
build(node*2+1, mid+1, r);
st[node] = comb(st[node*2], st[node*2+1]);
}
array<int, 4> qry(int node, int l, int r, int l1, int r1) {
if(l1 <= l && r <= r1) return st[node];
if(l > r1 || l1 > r) return {0, 0, 0, 0};
int mid = (l+r)/2;
return comb(qry(node*2, l, mid, l1, r1),
qry(node*2+1, mid+1, r, l1, r1));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
cin >> s;
int q;
cin >> q;
build(1, 0, n-1);
while(q--) {
int l, r;
cin >> l >> r; --l; --r;
array<int, 4> now = qry(1, 0, n-1, l, r);
cout << now[3] << '\n';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |