#include "bits/stdc++.h"
using namespace std;
const int N=5e5+1, K=19;
int n, q;
int a[N];
int mn[K][N], mx[K][N], nxt[K][N], h[K][N];
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n;
vector<int> a(n+1);
for(int i=1; i<=n; i++){
char c; cin >> c;
a[i]=(c=='C'?1:-1)+a[i-1];
}
for(int i=1; i<=n; i++){
mn[0][i]=mx[0][i]=a[i];
}
for(int j=1; j<K; j++){
for(int i=0; i+(1<<j)<=n+1; i++){
mn[j][i]=min(mn[j-1][i], mn[j-1][i+(1<<(j-1))]);
}
}
for(int j=1; j<K; j++){
for(int i=0; i+(1<<j)<=n+1; i++){
mx[j][i]=max(mx[j-1][i], mx[j-1][i+(1<<(j-1))]);
}
}
for(int i=0; i<=n+1; i++){
int j=i;
int _max=a[i];
for(int k=K-1; k>=0; k--){
if(j+(1<<k)<=n+1 && mn[k][j]>=a[i]){
_max=max(_max, mx[k][j]);
j+=(1<<k);
}
}
nxt[0][i]=j;
h[0][i]=_max-a[i];
// cout << "nxt " << i <<" " << j << " " << _max << "-" <<a[i] << "\n";
}
for(int k=1; k<K; k++){
for(int i=0; i+(1<<k)<=n+1; i++){
nxt[k][i]=nxt[k-1][nxt[k-1][i]];
h[k][i]=max(h[k-1][i], h[k-1][i+(1<<(k-1))]);
}
}
cin >> q;
while(q--){
int l,r;
cin >> l >> r;
int minv=1e9;
int i=l-1;
for(int k=K-1; k>=0; k--){
if(i+(1<<k)<=r+1){
minv=min(minv, mn[k][i]);
i+=(1<<k);
}
}
int ind=l-1;
int maxh=-1e9;
for(int p=K-1; p>=0; p--){
if(nxt[p][ind] && nxt[p][ind]<=r){
maxh=max(maxh, h[p][ind]);
ind=nxt[p][ind];
}
}
// max [lst, r]
i=ind;
int maxv=-1e9;
for(int k=K-1; k>=0; k--){
if(i+(1<<k)<=r+1){
maxv=max(maxv, mx[k][i]);
i+=(1<<k);
}
}
int peak=max(maxh, maxv-minv)+a[l-1];
// cout << minv << " " << maxv << " " << maxh << " " << peak << "\n";
cout << a[l-1]-minv + peak-(a[r]+a[l-1]-minv) << "\n";
}
}
// we're just a room full of strangers
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
