在咕了
Updated
基本算法1-2
把$p,j$看成$1,-1$ 前缀和维护区间
区间$[l,r]$合法当且仅当$sum[l]≤sum[i]≤sum[r]$
当存在$p>x$且$sum[x]>sum[p]$时$x$不合法
发现$x$满足单调性
单调队列维护然后在单调队列上二分
一个记录当前仍符合条件的右端点，一个记录已经被扫过的左端点，每当有元素从第一个栈里弹出时，就在第二个栈里二分找出符合两个条件的最远的左端点
code
1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5 const int maxn=1e6+10; 6 const int mod=1e9; 7 inline int read(){ 8 int f=1,x=0;char s=getchar(); 9 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 10 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 11 return f*x; 12 } 13 int n,a[maxn],sum[maxn],q1[maxn],q2[maxn]; 14 int r1,r2,ans=-1; 15 int find(int x){ 16 int tmp=-1; 17 int l=1,r=r2; 18 while(l<=r){ 19 int mid=(l+r)>>1; 20 if(q2[mid]>=x){ 21 r=mid-1;tmp=mid; 22 } 23 else l=mid+1; 24 } 25 // cout<<tmp<<" "; 26 return tmp==-1?-1:q2[tmp]; 27 } 28 void Max(int &x,int y){ 29 if(x==-1||x<y) x=y; 30 } 31 int main(){ 32 n=read(); 33 for(int i=1;i<=n;i++){ 34 char c;cin>>c; 35 if(c=='p')a[i]=1; 36 else a[i]=-1; 37 sum[i]=sum[i-1]+a[i]; 38 } 39 q1[++r1]=0;q2[++r2]=0; 40 for(int i=1;i<=n;i++){ 41 while(r1&&sum[q1[r1]]<=sum[i])r1--; 42 int L=q1[r1]+1; 43 if(!r1)L=0; 44 q1[++r1]=i; 45 while(r2&&sum[q2[r2]]>sum[i])r2--; 46 int tmp=find(L); 47 // cout<<tmp<<endl; 48 if(tmp==-1)tmp=i; 49 q2[++r2]=i; 50 51 Max(ans,i-tmp); 52 } 53 printf("%d",ans); 54 return 0; 55 } 56 } 57 signed main(){ 58 gengyf::main(); 59 return 0; 60 }