#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+7,N=5e5+1;
vector<int> pref(N),suf(N+1),t(4*N),t1(4*N),t2(4*N),t3(4*N);
int getans(int v,int tl,int tr,int l,int r){
if(l>r) return -INT_MAX;
if(l==tl && r==tr){
return t[v];
}
int tm=(tl+tr)/2;
return max(getans(v*2,tl,tm,l,min(r,tm)),getans(v*2+1,tm+1,tr,max(l,tm+1),r));
}
void build(int v,int tl,int tr){
if(tl==tr){
t[v]=pref[tl];
}else{
int tm=(tl+tr)/2;
build(v*2,tl,tm);
build(v*2+1,tm+1,tr);
t[v]=max(t[v*2],t[v*2+1]);
}
}
/////
int getans1(int v,int tl,int tr,int l,int r){
if(l>r) return -INT_MAX;
if(l==tl && r==tr){
return t1[v];
}
int tm=(tl+tr)/2;
return max(getans1(v*2,tl,tm,l,min(r,tm)),getans1(v*2+1,tm+1,tr,max(l,tm+1),r));
}
void build1(int v,int tl,int tr){
if(tl==tr){
t1[v]=suf[tl];
}else{
int tm=(tl+tr)/2;
build1(v*2,tl,tm);
build1(v*2+1,tm+1,tr);
t1[v]=max(t1[v*2],t1[v*2+1]);
}
}
////
int getans2(int v,int tl,int tr,int l,int r){
if(l>r) return INT_MAX;
if(l==tl && r==tr){
return t2[v];
}
int tm=(tl+tr)/2;
return min(getans2(v*2,tl,tm,l,min(r,tm)),getans2(v*2+1,tm+1,tr,max(l,tm+1),r));
}
void build2(int v,int tl,int tr){
if(tl==tr){
t2[v]=pref[tl];
}else{
int tm=(tl+tr)/2;
build2(v*2,tl,tm);
build2(v*2+1,tm+1,tr);
t2[v]=min(t2[v*2],t2[v*2+1]);
}
}
/////
int getans3(int v,int tl,int tr,int l,int r){
if(l>r) return INT_MAX;
if(l==tl && r==tr){
return t3[v];
}
int tm=(tl+tr)/2;
return min(getans3(v*2,tl,tm,l,min(r,tm)),getans3(v*2+1,tm+1,tr,max(l,tm+1),r));
}
void build3(int v,int tl,int tr){
if(tl==tr){
t3[v]=suf[tl];
}else{
int tm=(tl+tr)/2;
build3(v*2,tl,tm);
build3(v*2+1,tm+1,tr);
t3[v]=min(t3[v*2],t3[v*2+1]);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int n;
cin>>n;
string s;
cin>>s;
vector<int> v(n+1);
for(int i=1;i<=n;i++){
if(s[i-1]=='T') v[i]=1;
else v[i]=-1;
}
for(int i=1;i<=n;i++){
pref[i]=pref[i-1]+v[i];
}
for(int i=n;i>=1;i--){
suf[i]=suf[i+1]+v[i];
}
build(1,1,n);
build1(1,1,n);
build2(1,1,n);
build3(1,1,n);
//for(int i=1;i<=n;i++) cout<<pref[i]<<" ";
//cout<<endl;
//for(int i=1;i<=n;i++) cout<<suf[i]<<" ";
//cout<<endl;
int q;
cin>>q;
for(int i=1;i<=q;i++){
int l,r;
cin>>l>>r;
int ans=0;
ans=max(ans,getans(1,1,n,l,r)-pref[l-1]);
ans=max(ans,getans1(1,1,n,l,r)-suf[r+1]);
ans=max(ans,getans2(1,1,n,l,r)-pref[l-1]);
ans=max(ans,getans3(1,1,n,l,r)-suf[r+1]);
cout<<ans<<endl;
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
35592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
35592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
17 ms |
35592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
