#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
#define int long long
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
string ss;
struct ooga{
int t, l, r, mx;
};
ooga merge(ooga l, ooga r){
ooga res;
res.t=l.t+r.t;
res.l=max(l.l, l.t+r.l);
res.r=max(r.r, r.t+l.r);
res.mx=max({l.l+r.r, l.t+r.mx, r.t+l.mx});
return res;
}
struct node{
int s, e, m;
ooga val;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
if (s!=e){
l = new node(s, m);
r = new node(m+1, e);
val=merge(l->val, r->val);
}
else if (ss[s]=='T')val={1, 1, 1, 1};
else val={-1, 0, 0, 0};
}
ooga query(int left, int right){
if (s==left && e==right)return val;
if (right<=m)return l->query(left, right);
else if (left>m)return r->query(left, right);
else return merge(l->query(left, m), r->query(m+1, right));
}
}*st;
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q, a, b;
cin>>n>>ss;
ss=" "+ss;
st = new node(1, n);
cin>>q;
while (q--)cin>>a>>b, cout<<st->query(a, b).mx<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |