#include "bits/stdc++.h"
using namespace std;
#define mod 998244353
#define ll long long
#define N 24
#define maxn 200005
void solve(){
int n;
cin>>n;
string s;
cin>>s;
int sq=sqrt(n);
int p[n+5],pg[n+5],ss[n+5],ps[n+5];
int cur=0,mn=1e9;
for(int i=0; i<s.size(); i++){
if(s[i]=='C') cur++;
else cur--;
p[i]=cur;
mn=min(mn,cur);
if(i%sq==(sq-1)){
pg[i/sq]=mn;
mn=1e9;
}
}
cur=0;
for(int i=0; i<s.size(); i++){
if(s[s.size()-1-i]=='C') cur++;
else cur--;
ss[i]=cur;
mn=min(mn,cur);
if(i%sq==(sq-1)){
ps[i/sq]=mn;
mn=1e9;
}
}
int q;
cin>>q;
while(q--){
int l,r;
cin>>l>>r;
int x=1e9;
for(int i=l-1; i<r; i++){
if(i%sq==0 and (i+sq)<=r){
x=min(x,pg[i/sq]);
i=i+sq-1;
}else{
x=min(x,p[i]);
}
}
if(l>1){
x-=ss[l-2];
}
int ans=x;
x=1e9;
int yl=n-r,rr=n-l;
for(int i=yl; i<=rr; i++){
if(i%sq==0 and (i+sq)<=r){
x=min(x,ps[i/sq]);
i=i+sq-1;
}else{
x=min(x,ss[i]);
}
}
if(r<n){
x-=ss[n-r-1];
}
ans=min(ans,x);
cout<<abs(ans)<<'\n';
}
}
int main(){
// freopen("in.txt","w",stdout);
// freopen("out.txt","r",stdin);
ios_base::sync_with_stdio(0); cin.tie(0);
ll t=1;
// cin>>t;
while(t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |