#include <bits/stdc++.h>
using namespace std;
const int nx=5e5+5;
int n, vl[nx], q, l, r;
string str;
struct segtree
{
struct node
{
int l, r, sm, ans;
node(): l(0), r(0), sm(0), ans(-1e9){}
node(int x): l(x), r(x), sm(x), ans(x==1){}
friend node operator+(const node &a, const node &b)
{
if (a.ans==-1e9) return b;
if (b.ans==-1e9) return a;
node res;
res.l=max(a.l, a.sm+b.l);
res.r=max(a.r+b.sm, b.r);
res.sm=a.sm+b.sm;
res.ans=max({a.ans+b.sm, a.sm+b.ans, a.l+b.r, 0});
return res;
}
} d[4*nx];
void build(int l, int r, int i)
{
if (l==r) return d[i]=node(vl[l]), void();
int md=(l+r)/2;
build(l, md, 2*i);
build(md+1, r, 2*i+1);
d[i]=d[2*i]+d[2*i+1];
//cout<<l<<' '<<r<<' '<<d[i].l<<' '<<d[i].r<<' '<<d[i].sm<<' '<<d[i].ans<<'\n';
}
node query(int l, int r, int i, int ql, int qr)
{
if (qr<l||r<ql) return node();
if (ql<=l&&r<=qr) return d[i];
int md=(l+r)/2;
return query(l, md, 2*i, ql, qr)+query(md+1, r, 2*i+1, ql, qr);
}
} s;
int main()
{
cin.tie(NULL)->sync_with_stdio(false);
cin>>n>>str;
str=' '+str;
for (int i=1; i<=n; i++) vl[i]=(str[i]=='T')?1:-1;
s.build(1, n, 1);
cin>>q;
while (q--) cin>>l>>r, cout<<s.query(1, n, 1, l, r).ans<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
33372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
33372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
33372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
