Rockdu's Blog

6
jpjppj

4​​

 遇到个数有关的问题首先把j看做-1，p看做1。这样就是要从左往右从右往左每个位置的前缀和都非负，处理原数组[前/后]缀和为pre[i]、suf[i]。

 考虑对于位置i，先分别处理i向右最长能延伸到的地方和向左最长能延伸到的地方，记为R[i]和L[i]。这就相当于找到pre[i]右边/suf[i]左边第一个比他小的数。我们使用单调栈。

现在我们把所有位置按照L[i]从大到小排序。每一次维护加入当前L[i]以右的所有点。

考虑一个合法区间，一定是左端点R[i]在右端点或以后，右端点L[i]在左端点或以前，这样我们用一个线段树维护R[i]在[L,R]之间的点中，i的最小值是多少就可以了。因为我们每一次做后缀查询，可以使用树状数组。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
const int maxn = 1e6 + 5;
const int inf = 0x3f3f3f3f;
char s[maxn];
int pre[maxn], suf[maxn], a[maxn];
int L[maxn], R[maxn], len, ans;
typedef pair<int, int > pii;
pii Qs[maxn];
stack<int > stk, id;

namespace BIT {
    #define lowbit(x) ((x) & (-(x)))
    int t[maxn];
    void init() {memset(t, 0x3f, sizeof(t));}
    int query(int x) {
        int ans = inf;
        while(x) ans = min(ans, t[x]), x -= lowbit(x);
        return ans;
    }
    void edit(int x, int w) {
        while(x <= len) 
            t[x] = min(t[x], w), x += lowbit(x);
    }
}

void push(int * ans, int x, int pos, int p) {
    while(!stk.empty() && stk.top() > x) {
        ans[id.top()] = pos, stk.pop(), id.pop();
    }
    stk.push(x), id.push(p);
}

void clear(int * ans, int lim) {
    while(!stk.empty()) {
        ans[id.top()] = lim, stk.pop(), id.pop();
    }
}

int main() {
    scanf("%d", &len);
    scanf("%s", s + 1);
    BIT::init();
    for(register int i = 1; i <= len; ++i)
        a[i] = s[i] == 'p' ? 1 : -1;
    for(register int i = 1; i <= len; ++i)
        pre[i] = pre[i - 1] + a[i];
    for(register int i = len; i >= 1; --i)
        suf[i] = suf[i + 1] + a[i];
    push(R, 0, 0, 1); 
    for(register int i = 1; i < len; ++i) push(R, pre[i], i, i + 1);
    clear(R, len);
    push(L, 0, len + 1, len); 
    for(register int i = len; i > 1; --i) push(L, suf[i], i, i - 1);
    clear(L, 1);
    for(register int i = 1; i <= len; ++i)
        Qs[i] = make_pair(L[i], i);
    sort(Qs + 1, Qs + len + 1);
    int tp = len + 1;
    for(register int i = len; i >= 1; --i) {
        while(tp > Qs[i].first) 
            --tp, BIT::edit(len - R[tp] + 1, tp);
        int best = BIT::query(len - Qs[i].second + 1);
        ans = max(ans, max(Qs[i].second - best + 1, 0));
    }
    printf("%d", ans);
    return 0;
}