#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e5+10;
const int SS=1<<19;
int lazy[SS*2+10],seg[SS*2+10],seg2[SS*2+10],naj[N];
int sp[N],ans[N];
vector<pair<int,int> >zap[N];
void push(int v){
seg[v*2]+=lazy[v],seg[v*2+1]+=lazy[v];
lazy[v*2]+=lazy[v],lazy[v*2+1]+=lazy[v];
lazy[v]=0;
}
void upd(int pocz,int kon,int x,int p=0,int k=SS-1,int v=1){
if(p>kon or k<pocz) return;
if(p>=pocz and k<=kon){
seg[v]+=x,lazy[v]+=x;
return;
}
push(v);
upd(pocz,kon,x,p,(p+k)>>1,(v<<1)),upd(pocz,kon,x,((p+k)>>1)+1,k,(v<<1)+1);
seg[v]=min(seg[v<<1],seg[(v<<1)+1]);
}
int Query(int pocz,int kon,int p=0,int k=SS-1,int v=1){
if(p>kon or k<pocz) return INT_MAX;
if(p>=pocz and k<=kon) return seg[v];
push(v);
return min(Query(pocz,kon,p,(p+k)>>1,v<<1),Query(pocz,kon,((p+k)>>1)+1,k,(v<<1)+1));
}
void upd2(int a,int ind){
for(ind+=SS;ind>0;ind>>=1) seg2[ind]+=a;
}
int Query2(int a,int b){
int res=0;
for(a+=SS-1,b+=SS+1;(a>>1)!=(b>>1);a>>=1,b>>=1){
if(!(a&1)) res+=seg2[a+1];
if(b&1) res+=seg2[b-1];
}
return res;
}
void single(int x){
for(auto u:zap[x]){
int pom=Query(x,u.fi)-Query(u.fi+1,u.fi+1);
ans[u.se]=Query2(x,u.fi)+(pom>0?0:abs(pom));
}
if(sp[x]>sp[x-1]){
if(naj[x-1]!=-1) upd2(-1,naj[x-1]),upd(1,naj[x-1],-1);
if(naj[x]!=-1) upd2(1,naj[x]),upd(1,naj[x],1);
}
}
void solve(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
char a;
cin>>a;
if(a=='C') sp[i]=sp[i-1]+1;
else sp[i]=sp[i-1]-1;
}
deque<pair<int,int> >deq;
for(int i=n;i>=0;i--){
while(deq.size() and deq.back().fi>=sp[i]) deq.pop_back();
if(deq.size()) naj[i]=deq.back().se;
else naj[i]=-1;
deq.push_back({sp[i],i});
}
for(int i=1;i<=n;i++){
if(sp[i]>sp[i-1]) upd(1,i,1);
else upd(1,i,-1);
}
int curr=naj[0];
while(curr!=-1){
upd(1,curr,1);
upd2(1,curr);
curr=naj[curr];
}
int q;
cin>>q;
for(int i=1;i<=q;i++){
int a,b;
cin>>a>>b;
zap[a].push_back({b,i});
}
for(int i=1;i<=n;i++) single(i);
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}
int main(){
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
12188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
