#include<iostream>
#include<vector>
using namespace std;
const int N=5e5+1,X=1e6+1,TS=1<<20;
#define fi first
#define se second
#define pb push_back
int n,q;
int a[N];
int pre[N];
int nxt[X];
int f[X],v[X];
int sum[TS],mi[TS],cnt[TS];
int ans[N];
vector<pair<int,int> >qr[N];
void upd(int id,int l,int r,int pos,int v1,int v2){
if(l==r){
sum[id]+=v1;
mi[id]=min(sum[id],0);
cnt[id]+=v2;
return;
}
int mid=(l+r)/2;
if(pos<=mid) upd(id*2,l,mid,pos,v1,v2);
else upd(id*2+1,mid+1,r,pos,v1,v2);
sum[id]=sum[id*2]+sum[id*2+1];
mi[id]=min(mi[id*2+1],mi[id*2]+sum[id*2+1]);
cnt[id]=cnt[id*2]+cnt[id*2+1];
}
int qr1(int id,int l,int r,int ll,int rr){
if(l>rr || r<ll) return 0;
if(ll<=l && r<=rr) return cnt[id];
int mid=(l+r)/2;
return qr1(id*2,l,mid,ll,rr)+qr1(id*2+1,mid+1,r,ll,rr);
}
pair<int,int> qr2(int id,int l,int r,int ll,int rr){
if(l>rr || r<ll) return {0,0};
if(ll<=l && r<=rr) return {sum[id],mi[id]};
int mid=(l+r)/2;
pair<int,int>t1=qr2(id*2,l,mid,ll,rr),t2=qr2(id*2+1,mid+1,r,ll,rr);
return {t1.fi+t2.fi,min(t2.se,t1.se+t2.fi)};
}
int main(){
ios::sync_with_stdio(false);
cin >> n;
for(int i=1; i<=n ;i++){
char c;
cin >> c;
a[i]=(c=='C'?1:-1);
pre[i]=pre[i-1]+a[i];
if(f[pre[i]+n]==0) f[pre[i]+n]=i;
else nxt[v[pre[i]+n]]=i;
v[pre[i]+n]=i;
upd(1,1,n,i,a[i],0);
}
cin >> q;
for(int i=1; i<=q ;i++){
int l,r;
cin >> l >> r;
qr[l].pb({r,i});
}
for(int i=0; i<n ;i++){
if(f[i]!=0) upd(1,1,n,f[i],1,1);//a[f[i]]=-1
}
for(int i=1; i<=n ;i++){
for(auto cur:qr[i]){
ans[cur.se]=qr1(1,1,n,i,cur.fi)-qr2(1,1,n,i,cur.fi).se;
}
f[pre[i]+n]=nxt[i];
if(a[i]==-1) upd(1,1,n,i,-1,-1);
else if(nxt[i]!=0) upd(1,1,n,nxt[i],1,1);
}
for(int i=1; i<=q ;i++) cout << ans[i] << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
