#include<bits/stdc++.h>
using namespace std;
using I=int;
using C=char;
const I N=500000;
C fans[N];
pair<I,I>segs1[2*N];
pair<I,I>segs2[2*N];
I n;
pair<I,I>cmb1(pair<I,I>a,pair<I,I>b){
auto[ic1,it1]=a;auto[ic2,it2]=b;
return{ic1+ic2-min(ic1,it2),it1+it2-min(ic1,it2)};
}
pair<I,I>cmb2(pair<I,I>a,pair<I,I>b){
auto[dc1,dt1]=a;auto[dc2,dt2]=b;
return{dc1+dc2-min(dt1,dc2),dt1+dt2-min(dt1,dc2)};
}
void asn1(I i){
segs1[i+n].first++,segs2[i+n].first++;
}
void asn2(I i){
segs1[i+n].second++,segs2[i+n].second++;
}
void bld(){
for(I i=n-1;i>0;i--)segs1[i]=cmb1(segs1[i<<1],segs1[i<<1|1]);
for(I i=n-1;i>0;i--)segs2[i]=cmb2(segs2[i<<1],segs2[i<<1|1]);
}
I qry1(I l,I r){
pair<I,I>lrs={0,0},rrs={0,0};
for(l+=n,r+=n;l<r;l>>=1,r>>=1){
if(l&1)lrs=cmb1(lrs,segs1[l++]);
if(r&1)rrs=cmb1(segs1[--r],rrs);
}
return cmb1(lrs,rrs).second;
}
I qry2(I l,I r){
pair<I,I>lrs={0,0},rrs={0,0};
for(l+=n,r+=n;l<r;l>>=1,r>>=1){
if(l&1)lrs=cmb2(lrs,segs2[l++]);
if(r&1)rrs=cmb2(segs2[--r],rrs);
}
return cmb2(lrs,rrs).second;
}
I fnd1(I x,I y){
I l=x,r=y+1;
while(l<r){
I m=l+(r-l)/2;
qry1(x,m)>=qry1(x,y+1)?r=m:l=m+1;
}
return l;
}
I fnd2(I x,I y){
I l=x,r=y+1;
while(l<r){
I m=l+(r-l+1)/2;
qry2(m,y)>=qry2(x,y+1)?l=m:r=m-1;
}
return l;
}
I main(){
cin.tie(0)->sync_with_stdio(0);
cin>>n;
cin>>fans;
for(I i=0;i<n;i++)fans[i]=='C'?asn1(i):asn2(i);
bld();
I q;cin>>q;
while(q--){
I l,r;cin>>l>>r,l--,r--;
I x=fnd1(l,r),y=fnd2(l,r);
printf("%i\n",qry1(l,r+1)+qry2(l,r+1)-min(qry1(l,r+1)-qry1(l,y),qry2(l,r+1)-qry2(x,r+1)));
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
