1. 题目

传送门=￣ω￣=

2. 题解

额。。。

首先把 j 设为 $-1$，p 设为 $1$，求前缀和，设为 $d$数组。

若 $[l, r]$为符合条件子串，则 $d[l – 1] \leq d[i](i \in [l, r])$且 $d[r] \geq d[i](i \in [l, r])$

求出每个 $d[i]$的后面第一个比它小的元素的位置 $right[i]$和前面第一个比它大的元素的位置 $left[i]$。这个用单调栈。

然后枚举 $d[l – 1]$，在 $[l, right[i]]$内二分出满足 $left[j] \leq l – 1$的最大的 $j$，用 $j – l + 1$更新答案。

代码：

#include <bits/stdc++.h>

#define NS (1000005)
#define FIR first
#define SEC second
#define LS(a) (a << 1)
#define RS(a) (a << 1 | 1)

using namespace std;

typedef pair<int, int> PII;

int n, d[NS], lft[NS], rit[NS], ans;

char str[NS];

stack<PII> st;

struct N {int l, r, d;} e[NS << 2];

void Build(int l, int r, int a)
{
    e[a].l = l, e[a].r = r;
    if (l == r) {e[a].d = lft[l]; return;}
    int mid = (l + r) >> 1;
    Build(l, mid, LS(a)), Build(mid + 1, r, RS(a));
    e[a].d = min(e[LS(a)].d, e[RS(a)].d);
}

int Query(int r, int v, int a)
{
    if (e[a].l > r || e[a].d > v) return 0;
    if (e[a].l == e[a].r) return e[a].l;
    if (e[RS(a)].d <= v)
    {
        int tmp = Query(r, v, RS(a));
        if (tmp) return tmp;
    }
    if (e[LS(a)].d <= v) return Query(r, v, LS(a));
    return 0;
}

int main(int argc, char const* argv[])
{
    scanf("%d%s", &n, str + 1);
    for (int i = 1; i <= n; i += 1)
        if (str[i] == 'p') d[i] = d[i - 1] + 1;
        else d[i] = d[i - 1] - 1;
    st.push(PII(INT_MAX, 0));
    for (int i = 1; i <= n; i += 1)
    {
        while (st.top().FIR <= d[i]) st.pop();
        lft[i] = st.top().SEC, st.push(PII(d[i], i));
    }
    while (!st.empty()) st.pop();
    st.push(PII(INT_MIN, n + 1));
    for (int i = n; i >= 0; i -= 1)
    {
        while (st.top().FIR >= d[i]) st.pop();
        rit[i] = st.top().SEC, st.push(PII(d[i], i));
    }
    Build(1, n, 1);
    for (int i = 0; i < n; i += 1)
        ans = max(ans, Query(rit[i], i, 1) - i);
    printf("%d\n", ans);
    return 0;
}