#include<bits/stdc++.h>
using namespace std;
const int N=1<<20;
string st;
struct node{
int ans,mxl,mxr,sum;
friend node operator+(const node &a,const node &b){
node ret;
if(a.ans==-1e9){ret=b; return ret;}
if(b.ans==-1e9){ret=a; return ret;}
ret.sum=a.sum+b.sum;
ret.mxl=max({0,a.mxl,b.mxl+a.sum});
ret.mxr=max({0,a.mxr+b.sum,b.mxr});
ret.ans=max({a.ans+b.sum,a.sum+b.ans,a.mxl+b.mxr});
return ret;
}
void pt(){
cout<<ans <<" " <<mxl <<" " <<mxr <<" " <<sum <<" ";
}
}s[N],out;
void build(int l,int r,int idx){
if(l==r){
if(st[l]=='C'){
s[idx].sum=s[idx].ans=-1;
s[idx].mxl=s[idx].mxr=0;
}
else{
s[idx].sum=s[idx].ans=1;
s[idx].mxl=s[idx].mxr=0;
}
// cout<<l <<" " <<r <<" ";
// s[idx].pt();
// cout<<"\n";
return;
}
int m=(l+r)/2;
build(l,m,idx*2);
build(m+1,r,idx*2+1);
s[idx]=s[idx*2]+s[idx*2+1];
// cout<<l <<" " <<r <<" ";
// s[idx].pt();
//cout<<"\n";
}
node query(int l,int r,int idx,int a,int b){
if(b<l || a>r) return out;
if(a<=l && b>=r) return s[idx];
int m=(l+r)/2;
return query(l,m,idx*2,a,b)+query(m+1,r,idx*2+1,a,b);
}
int main(){
int n,q;
out.ans=-1e9;
cin>>n >>st >>q;
build(0,n-1,1);
while(q--){
int a,b;
cin>>a >>b;
node tmp=query(0,n-1,1,a-1,b-1);
int ans=0;
ans=max(ans,tmp.ans);
cout<<ans <<"\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... |