题意：

给定长度为n的字符串，每一位只会是p或j。
求一个最长子串，使得不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。
输出最长子串的长度

数据范围：n<=1e6

解法：

将p视为1，j视为-1，那么问题就变为求一个最长子串，满足这个子串的前缀和与后缀和都是>=0的

容易想到求出以每个位置为起点能向左和向右扩展的最大位置L[]和R[]，求法：
计算前缀和，对于第i个位置，设其左边第一个大于sum[i]的位置pos那么L[i]=pos+1
怎么找左边第一个满足条件的位置呢？可以用last[k]记录上一次k出现的位置，
然后利用last[]找到左边第一个大于sum[i]的位置，假如当前sum[i]=S,那么L[i]=last[S+1]+1。
计算R[]则利用后缀和
注意：因为sum[]会出现负数，所以要么last用map，要么给last设置偏移量。实测map会超时，我的代码把偏移量设为了n。（也许unordered_map不会超时，没试过）

如果串[x,y]是合法的，那么显然L[y]<=x，R[x]>=y，我们要的答案就是满足这个条件的最大的y-x+1
发现条件只有二维，那么可以通过枚举的方法消除一维的限制。
发现当x增加时，满足L[y]<=x的y仍然满足L[y]<=x+1，是单调的
因此对每个位置按L[]从小到大排序，然后从小到达枚举x，将满足L[y]<=x的所有y加入树状数组（维护前缀max）
然后查询小于等于R[x]的y的最大值y1，用y1-x+1更新答案。枚举完所有x后即可计算出答案。
注意：x和y位置上一定是字母p（区间端点一定是p，即以p开始）

code：

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int maxm=2e6+5;
struct BIT{int c[maxm];int lowbit(int i){return i&-i;}void add(int i,int t){while(i<maxm)c[i]=max(c[i],t),i+=lowbit(i);}int ask(int i){int ans=0;while(i)ans=max(ans,c[i]),i-=lowbit(i);return ans;}
}T;
struct Node{int y,ly;friend bool operator<(Node a,Node b){return a.ly<b.ly;}
}e[maxm];
char s[maxm];
int a[maxm];
int sum[maxm];
int last[maxm];
int L[maxm],R[maxm];
int n;
signed main(){scanf("%d",&n);scanf("%s",s+1);for(int i=1;i<=n;i++){if(s[i]=='p')a[i]=1;else a[i]=-1;}//计算L[],last[]偏移量为nfor(int i=1;i<=n;i++){sum[i]=sum[i-1]+a[i];if(last[sum[i]+1+n])L[i]=last[sum[i]+1+n]+1;else L[i]=1;last[sum[i]+n]=i;}//计算R[]for(int i=0;i<=n*2;i++)last[i]=0;for(int i=n;i>=1;i--){sum[i]=sum[i+1]+a[i];if(last[sum[i]+1+n])R[i]=last[sum[i]+1+n]-1;else R[i]=n;last[sum[i]+n]=i;}//按L[]排序int cnt=0;for(int i=1;i<=n;i++){if(a[i]==1){//开头一定要是pe[++cnt]={i,L[i]};}}sort(e+1,e+1+cnt);//int k=1;int ans=0;for(int x=1;x<=n;x++){while(k<=cnt&&e[k].ly<=x){T.add(e[k].y,e[k].y);k++;}if(a[x]==1){ans=max(ans,T.ask(R[x])-x+1);}}printf("%d\n",ans);return 0;
}

---