#include<bits/stdc++.h>
using namespace std;
int seg[2000001],lazy[2000001];
void build(int p,int l,int r){
if(l==r){
seg[p] = 0;return ;
}
int md = (l+r)/2;
build(p*2,l,md);build(p*2+1,md+1,r);
seg[p] = 0;
}
void prop(int p,int l,int r){
seg[p]+=lazy[p];
if(l!=r){
lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
}
lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,int val){
prop(p,l,r);
if(l>=lq&&r<=rq){
lazy[p]+=val;
prop(p,l,r);
return ;
}
if(l>rq||r<lq)return ;
int md = (l+r)/2;
update(p*2,l,md,lq,rq,val);update(p*2+1,md+1,r,lq,rq,val);
seg[p] = min(seg[p*2],seg[p*2+1]);
}
int query(int p,int l,int r,int lq,int rq){
prop(p,l,r);
if(l>=lq&&r<=rq)return seg[p];
if(l>rq||r<lq)return 1e9;
int md = (l+r)/2;
return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
//BIT Fenwick tree
int n ;
int bit[500001]={0};
void add(int e,int v){
while(e<=n){
bit[e]+=v;
e+=e&-e;
}
}
long long sum(int e){
long long res = 0;
while(e>=1){
res+=bit[e];
e -= e&-e;
}
return res;
}
//end BIT
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
string s;cin>>n>>s;
build(1,1,n);
for(int i = 0;i<n;i++){
if(s[i]=='T'){
update(1,1,n,1,i+1,-1);
}else update(1,1,n,1,i+1,1);
}
int q;cin>>q;
int lol[q+1] = {0};
vector<pair<pair<int,int>,int>> qu;
for(int i = 1;i<=q;i++){
int l,r;cin>>l>>r;
l--;r--;
qu.push_back({{l,r},i});
}
sort(qu.begin(),qu.end());reverse(qu.begin(),qu.end());
int idx = n-1;
stack<int> st;
for(auto i:qu){
while(idx>=i.first.first){
if(s[idx]=='T'){
st.push(idx);
update(1,1,n,1,idx+1,1);
add(idx+1,1);
}else{
if(st.size()){
update(1,1,n,1,st.top()+1,-1);
add(st.top()+1,-1);
st.pop();
}
}
idx--;
}
int ans = query(1,1,n,i.first.first+1,i.first.second+1);
if(i.first.second+1<n){
ans-=query(1,1,n,i.first.second+2,i.first.second+2);
}
lol[i.second] = sum(i.first.second+1)-sum(i.first.first)+min(0,abs(ans));
}
for(int i = 1;i<=q;i++){
cout<<lol[i]<<"\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
