#include<bits/stdc++.h> using namespace std; using ll = long long; #define fi first #define se second const int N = 5e5+5; const int LG = 20; int spt[N][LG],mnval[N][LG]; int mnr[N][LG]; int lg2[N]; int a[N],pre[N],suf[N],nxt[N]; int n,q; int getmin(int l,int r){ if(l>r) return 1e9; int lg=lg2[r-l+1]; return min(mnr[l][lg],mnr[r-(1<<lg)+1][lg]); } signed main(){ ios::sync_with_stdio(false);cin.tie(nullptr); if(fopen("text.inp","r")){ freopen("text.inp","r",stdin); } cin>>n; lg2[1]=0; for(int i=2;i<=n;i++) lg2[i]=lg2[i/2]+1; for(int i=1;i<=n;i++){ char c; cin>>c; if(c == 'C') a[i]=1; else a[i]=-1; pre[i]=pre[i-1]+a[i]; } for(int i=n;i>=1;i--) suf[i]=suf[i+1]+a[i]; for(int i=1;i<=n;i++) mnr[i][0]=suf[i]; for(int lg=1;lg<LG;lg++){ for(int i=1;i+(1<<lg)-1<=n;i++){ mnr[i][lg] = min(mnr[i][lg-1],mnr[i+(1<<(lg-1))][lg-1]); } } map<int,int> mp; for(int lg=0;lg<LG;lg++) spt[n+1][lg]=n+1; for(int i=n;i>=1;i--){ mp[pre[i]]=i; if(mp.find(pre[i]-1) != mp.end()){ spt[i][0]=mp[pre[i]-1]; mnval[i][0]=getmin(i+1,spt[i][0]-1); if(mnval[i][0] != 1e9) mnval[i][0]++; }else{ spt[i][0]=n+1; mnval[i][0]=1e9; } if(mp.find(pre[i-1]-1) != mp.end()){ nxt[i]=mp[pre[i-1]-1]; }else nxt[i]=n+1; } for(int lg=1;lg<LG;lg++){ for(int i=1;i<=n;i++){ if(spt[i][lg-1] != n+1){ spt[i][lg]=spt[spt[i][lg-1]][lg-1]; mnval[i][lg] = min(mnval[spt[i][lg-1]][lg-1],mnval[i][lg-1] + (1<<(lg-1))); }else{ spt[i][lg]=n+1; mnval[i][lg]=1e9; } } } cin>>q; while(q--){ int l,r; cin>>l>>r; int p=l; int ans=0; int sum=0; int mn=1e9; p=nxt[p]; for(int lg=LG-1;lg>=0;lg--){ if(spt[p][lg] <= r){ sum += (1<<lg); p=spt[p][lg]; } } p=nxt[l]; if(nxt[l] <= r){ sum++; ans++; } for(int lg=LG-1;lg>=0;lg--){ if(spt[p][lg] <= r){ ans += (1<<lg); mn=min(mn,mnval[p][lg] + sum-ans); p=spt[p][lg]; } } //cerr<<nxt[l]<<'\n'; mn = min(mn,getmin(l,min(r,nxt[l]-1))+sum); mn = min(mn,getmin(p+1,r)); mn -= suf[r+1]; if(mn < 0) ans += -mn; cout<<ans<<'\n'; } }

election.cpp: In function 'int main()':
election.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen("text.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~