题目链接
题解
容易想到用前缀和搞
如果我们令(p)为(1)，(j)为(-1)，记前缀和为(s[i])
我们就是要找到一段区间([l,r])，使得
[forall i in [l,r] quad s[i] - s[l - 1] ge 0
]
[forall i in [l - 1,r - 1] quad s[r] - s[i] ge 0
]
所以说(s[l - 1])是区间([l - 1,r])的最小值，(s[r])是区间([l - 1,r])的最大值
问题转化为了：我们需要找到最小值在左端，最大值在右端的最长区间
按照寻找最优区间的套路，我们枚举左端点，可以利用单调栈求出左端点满足要求的区间
然后在这个区间内查找最大值的位置【如果多个相同则取最右】，来更新答案
为什么一定是最大值的位置最优？因为最大值右边的一定不符，最大值左边的一定比当前答案小
复杂度(O(nlogn))，线段树没太多操作，甚至不用修改，所以常数很小，可以放心过
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int maxn = 1000005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int mx[maxn << 2],A[maxn];
inline void upd(int u){
mx[u] = A[mx[ls]] > A[mx[rs]] ? mx[ls] : mx[rs];
}
void build(int u,int l,int r){
if (l == r) mx[u] = l;
else {
int mid = l + r >> 1;
build(ls,l,mid);
build(rs,mid + 1,r);
upd(u);
}
}
int query(int u,int l,int r,int L,int R){
if (l >= L && r <= R) return mx[u];
int mid = l + r >> 1;
if (mid >= R) return query(ls,l,mid,L,R);
else if (mid < L) return query(rs,mid + 1,r,L,R);
else {
int t1 = query(ls,l,mid,L,R),t2 = query(rs,mid + 1,r,L,R);
return A[t1] > A[t2] ? t1 : t2;
}
}
int n,st[maxn],top,r[maxn];
int main(){
n = read(); char c = getchar();
while (!isalpha(c)) c = getchar();
REP(i,n){
A[i] = A[i - 1] + (c == 'p' ? 1 : -1);
c = getchar();
}
build(1,1,n);
st[top = 1] = n;
int ans = 0,x;
for (int i = n - 1; ~i; i--){
while (top && A[i] <= A[st[top]]) top--;
if (!top) r[i] = n;
else r[i] = st[top] - 1;
st[++top] = i;
if (i + 1 <= r[i]){
x = query(1,1,n,i + 1,r[i]);
ans = max(ans,x - i);
}
}
printf("%d
",ans);
return 0;
}