题意：有一个长度为n的字符串，每一位只会是p或j。你需要取出一个子串S（注意不是子序列），使得该子串不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。如果你的子串是最长的，那么称之为完美字符子串。求完美字符子串的长度。

乍一看比较水，然而差点没想出来。

考虑处理前缀和，p+1 j-1 那么对于一段区间[l,r]只要每一个i∈[l,r]满足presum[i]-presum[l-1]>=0即满足题意

1.单调队列预处理每个位置向前/后走的最远位置 记为f[i]/g[i]

2.枚举区间的左端点L,那么对于所有R∈[i,f[i]]找到最靠右的R满足g[R]<=i

3.R何可以通过向右移动cur优化,查找R可以用线段树优化

Code:

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;

int n, f[MAXN], g[MAXN], sum1[MAXN], sum2[MAXN];

char s[MAXN];

int cnt, st[MAXN];

void solve1()

{

	for(int i = 1; i <= n; i++)

		if(s[i] == 'p') st[++cnt] = i;

		else

		{

			while(cnt && sum1[st[cnt]] - sum1[i] > 1)

				f[st[cnt--]] = i-1;

		}

	while(cnt) f[st[cnt--]] = n;

}

void solve2()

{

	for(int i = n; i >= 1; i--)

		if(s[i] == 'p') st[++cnt] = i;

		else

		{

			while(cnt && sum2[st[cnt]] - sum2[i] > 1)

				g[st[cnt--]] = i+1;

		}

	while(cnt) g[st[cnt--]] = 1;

}

int mn[MAXN*4];

void build(int i, int l, int r)

{

	if(l == r)

	{

		mn[i] = (g[l] == 0) ? 0x7f7f7f7f : g[l];

		return;

	}

	int mid = (l + r) >> 1;

	build(i*2, l, mid);

	build(i*2+1, mid+1, r);

	mn[i] = min(mn[i*2], mn[i*2+1]);

}

int find(int i, int l, int r, int x, int y, int k)

{

	if(y < l || x > r || mn[i] > k) return -1;

	if(l == r) return mn[i] <= k ? l : -1;

	int mid = (l + r) >> 1;

        int tmp = find(i*2+1, mid+1, r, x, y, k);

        if(tmp != -1) return tmp;

	return find(i*2, l, mid, x, y, k);

}

int main ()

{

	scanf("%d%s", &n, s+1);

	for(int i = 1; i <= n; i++)

        sum1[i] = sum1[i-1] + (s[i] == 'p' ? 1 : -1);

	solve1();

	for(int i = n; i >= 1; i--)

        sum2[i] = sum2[i+1] + (s[i] == 'p' ? 1 : -1);

	solve2();

	build(1, 1, n);

	int cur = 1, Ans = 0;

	for(int i = 1; i <= n; i++) if(f[i])

	{

		int pos = find(1, 1, n, cur=max(cur, i), f[i], i);

		if(pos == -1) continue;

		Ans = max(Ans, pos - i + 1); cur = pos+1;

	}

	printf("%d\n", Ans);

}