#include <bits/stdc++.h>
using namespace std;
int const MAX=500005;
struct node{
int rez,ult,maxim,minim;
};
struct AINT{
int n;
node v[4*MAX];
node combine(node a,node b){
return {
.rez=max(max(a.rez,b.rez),b.maxim+a.ult-a.minim),
.ult=a.ult+b.ult,
.maxim=max(a.maxim,b.maxim+a.ult),
.minim=min(a.minim,b.minim+a.ult)
};
}
void update(int nod,int st,int dr,int poz,int val){
if(st==dr)
v[nod]={0,val,val,val};
else{
int mij=(st+dr)/2;
if(poz<=mij)
update(2*nod,st,mij,poz,val);
else
update(2*nod+1,mij+1,dr,poz,val);
v[nod]=combine(v[2*nod],v[2*nod+1]);
}
}
node query(int nod,int st,int dr,int a,int b){
if(a<=st && dr<=b)
return v[nod];
node ans={0,0,0,0};
int mij=(st+dr)/2;
if(a<=mij)
ans=combine(ans,query(2*nod,st,mij,a,b));
if(b>mij)
ans=combine(ans,query(2*nod+1,mij+1,dr,a,b));
return ans;
}
}aint;
void read(){
cin>>aint.n;
int i;
for(i=1;i<=aint.n;++i){
char ch;
cin>>ch;
if(ch=='C')
aint.update(1,1,aint.n,i,1);
else
aint.update(1,1,aint.n,i,-1);
}
}
void process_queries(){
int q;
cin>>q;
int i;
for(i=1;i<=q;++i){
int st,dr;
cin>>st>>dr;
node ans=aint.query(1,1,aint.n,st,dr);
cout<<max(ans.rez,ans.maxim)-ans.ult<<'\n';
}
}
int main()
{
read();
process_queries();
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... |