#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll MX = 1<<19;
const ll INF = 1e18;
#define f first
#define s second
ll n,q,a[MX],ans[MX];
string s;
vector<pll> query[MX];
vector<pll> vec;
template<class T,ll SZ> struct maxtree//with range update
{
ll mx[2*SZ], lazy[2*SZ]; // set SZ to a power of 2
maxtree()
{
memset(mx,0,sizeof mx);
memset(lazy,0,sizeof lazy);
}
void propagate(ll l,ll r, ll ind)
{
if(lazy[ind])
{
mx[ind] += lazy[ind];
if(l!=r)
{
lazy[ind*2]+=lazy[ind];
lazy[ind*2+1]+=lazy[ind];
}
lazy[ind] = 0;
}
}
void pull(ll ind)
{
mx[ind] = max(mx[ind*2],mx[ind*2+1]);
}
T merge(T left,T right)
{
return max(left,right);
}
void update(ll l,ll r,ll s,ll e,ll ind,ll val)
{
propagate(l,r,ind);
if(e<l||r<s)
return;
if(s<=l&&r<=e)
{
lazy[ind]+=val;
propagate(l,r,ind);
return;
}
ll mid = (l+r)>>1;
update(l,mid,s,e,ind*2,val);
update(mid+1,r,s,e,ind*2+1,val);
pull(ind);
}
T query(ll l,ll r,ll s,ll e, ll ind)
{
propagate(l,r,ind);
if(e<l || r<s)
return -INF;
if(s<=l&&r<=e)
{
//cout<<l<<" "<<r<<" "<<s<<" "<<e<<" "<<ind<<" "<<mx[ind]<<"===\n";
return mx[ind];
}
ll mid = (l+r)>>1;
return merge(query(l,mid,s,e,ind*2),query(mid+1,r,s,e,ind*2+1));
}
};
template<class T,ll SZ> struct sumtree//without range update
{
ll v[2*SZ]; // set SZ to a power of 2
sumtree()
{
memset(v,0,sizeof v);
}
T merge(T left, T right)
{
return left+right;
}
void update(ll l,ll r,ll x,ll ind,ll val)
{
//cout<<l<<" "<<r<<" "<<x<<" "<<ind<<" "<<val<<"\n";
if(x<l||r<x)
return;
if(l==r)
{
v[ind]+=val;
return;
}
ll mid = (l+r)>>1;
update(l,mid,x,ind*2,val);
update(mid+1,r,x,ind*2+1,val);
v[ind] = merge(v[ind*2],v[ind*2+1]);
}
T query(ll l,ll r,ll s,ll e, ll ind)
{
//cout<<l<<" "<<r<<" "<<s<<" "<<e<<" "<<ind<<"\n";
if(e<l || r<s)
return 0;
if(s<=l&&r<=e)
return v[ind];
ll mid = (l+r)>>1;
return merge(query(l,mid,s,e,ind*2),query(mid+1,r,s,e,ind*2+1));
}
};
maxtree<ll, MX> mtree;
sumtree<ll, MX> stree;
void solve(ll x)
{
while(vec.size()&&vec.back().f >= a[x])
{
stree.update(0,MX-1,vec.back().s,1,-1);
mtree.update(0,MX-1,vec.back().s,MX-1,1,-1);
vec.pop_back();
}
for(auto z:query[x])
{
ll m1 = mtree.query(0,MX-1,x,z.f,1);
ll m2 = mtree.query(0,MX-1,z.f,z.f,1);
ans[z.s] = stree.query(0,MX-1,x+1,z.f,1)+m1-m2;
//cout<<stree.query(0,MX-1,x+1,z.f,1)<<"======"<<m1<<"====="<<m2<<"===="<<x<<"=====\n";
}
if(x)
{
stree.update(0,MX-1,x,1,1);
mtree.update(0,MX-1,x,MX-1,1,1);
vec.push_back({a[x],x});
}
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(NULL);
cin>>n;
cin>>s;
for(ll i=0;i<n;i++)
{
if(s[i]=='C')
a[i+1] = a[i]+1;
else
a[i+1] = a[i]-1;
}
for(ll i=0;i<n+1;i++)
mtree.update(0,MX-1,i,i,1,a[i]);
cin>>q;
for(ll i=0;i<q;i++)
{
ll l,r;
cin>>l>>r;
query[l-1].push_back({r,i});
}
for(ll i=n;i>=0;i--) solve(i);
for(ll i=0;i<q;i++) cout<<ans[i]<<"\n";
}
Compilation message
File "election.py", line 2
using namespace std;
^
SyntaxError: invalid syntax
