是的我BZOJ又没卡过……懒得卡了。
参考：https://blog.csdn.net/zqh_wz/article/details/52887289
参考的$O(n)$预处理我反正没看懂……设$L[i]$为i向左能够取到的最远位置，$R[i]$同理。
则我们$O(nlogn)$就能求出来，就是前缀和维护一个st表区间最小值，这样二分答案只要check这个区间最小值+前面没有取到的贡献就行了。
判断的话实际转换成求$L,R$必须满足$L[R]<=L$ $R<=R[L]$
我们可以对R进行排序然后树状数组维护L，具体的做法可以看代码画个图，你就知道为啥对了。
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+;
const int INF=1e9;
char s[N];
int n,a[N],tr[N];
int f[N][],lg[N],L[N],R[N];
inline int qpow(int a){return <<a;}
inline int qry(int l,int r){
int len=r-l+,k=lg[len],h=qpow(k);
return min(f[l][k],f[r-h+][k]);
}
void st(){
for(int j=;j<=lg[n];j++)
for(int i=;i<=n;i++){
if(i+qpow(j)->n)break;
f[i][j]=min(f[i][j-],f[i+qpow(j-)][j-]);
}
}
struct node{
int R,id;
bool operator <(const node &a)const{
return R<a.R;
}
}g[N];
inline int lowbit(int t){return t&-t;}
inline void add(int x,int y){
for(int i=x;i<=n;i+=lowbit(i))tr[i]=max(tr[i],y);
}
inline int query(int x){
int res=;
for(int i=x;i;i-=lowbit(i))res=max(res,tr[i]);
return res;
}
int main(){
scanf("%d%s",&n,s+);
for(int i=;i<=n;i++)
if(s[i]=='p')a[i]=a[i-]+;
else a[i]=a[i-]-;
for(int i=;i<=n;i++){
lg[i]=lg[i-];
if((<<lg[i]+)==i)lg[i]++;
f[i][]=a[i];
}
st();
for(int i=;i<=n;i++){
int l=i-,r=n;
while(l<r){
int mid=(l+r+)>>;
if(qry(i,mid)-a[i-]>=)l=mid;
else r=mid-;
}
g[i].R=l,g[i].id=i;
} for(int i=;i<=n;i++)
if(s[n-i+]=='p')a[i]=a[i-]+;
else a[i]=a[i-]-;
for(int i=;i<=n;i++)f[i][]=a[i];
st();
for(int i=;i<=n;i++){
int l=i-,r=n;
while(l<r){
int mid=(l+r+)>>;
if(qry(i,mid)-a[i-]>=)l=mid;
else r=mid-;
}
L[n-i+]=n-l+;
} sort(g+,g+n+);
int now=,ans=;
for(int i=;i<=n;i++){
while(now<=g[i].R){
add(L[now],now);now++;
}
int r=query(g[i].id);
ans=max(ans,r-g[i].id+);
}
printf("%d\n",ans);
return ;
}