题意

长度为\(n(1 \le n \le 1000000)\)的\(01\)字符串。找一个最长的连续子串\(S\)，使得不管是从左往右还是从右往左取，都保证每时每刻已取出的\(1\)的个数不小于\(0\)的个数。

分析

首先对\(i\)求出\(l_i, r_i\)，\(l_i\)表示在区间\([l_i, i]\)从左往右一直取，\(1\)的个数总是不少于\(0\)的个数的最远\(l_i\)。\(r_i\)同理。由于前缀和前后差绝对值为\(1\)，所以我们可以开一个数组在\(O(n)\)内求出这\(l_i, r_i\)（比如求\(l_i\)就是我们只需要找一个满足\(sum_i+1=sum_j, j < i\)的最大\(j\)）

然后我们对\(l_i\)升序排序（假设得到的顺序是\(b_i\)）。然后从左到右扫过去，当前在\(i\)位置，每次更新满足\(l_{b_j} \le i\)的所有的\(b_j\)到区间\([b_j, n]\)，然后对于\(i\)，则向右能拓展到的位置就是区间\([1, i]\)的最大值。

题解

维护这个前缀最大值用个\(bit\)就行了。复杂度\(O(nlogn)\)。

#include 
    
     using namespace std;const int N=1000005;int n, a[N], b[N+N], c[N+N], s1[N], s2[N], l[N], r[N], mx[N];void add(int x, int g) {    for(; x<=n; x+=x&-x) {        mx[x]=max(mx[x], g);    }}int getmx(int x) {    int y=0;    for(; x; x-=x&-x) {        y=max(y, mx[x]);    }    return y;}void isort(int *y, int *x) {    for(int i=0; i<=n; ++i) c[i]=0;    for(int i=1; i<=n; ++i) c[y[i]]++;    for(int i=1; i<=n; ++i) c[i]+=c[i-1];    for(int i=1; i<=n; ++i) x[c[y[i]]--]=i;}int main() {    scanf("%d\n", &n);    for(int i=1; i<=n; ++i) {        a[i]=getchar()=='p'?1:-1;    }    for(int i=1, j=n; i<=n; ++i, --j) {        s1[i]=s1[i-1]+a[i];        s2[j]=s2[j+1]+a[j];        b[s1[i]+N]=b[s1[i]+1+N]=-1;        c[s2[j]+N]=c[s2[j]+1+N]=n+2;    }    for(int i=1, j=n; i<=n; ++i, --j) {        if(a[i]==1) {            l[i]=b[s1[i]+1+N]+2;        }        if(a[j]==1) {            r[j]=c[s2[j]+1+N]-2;        }        b[s1[i]+N]=i;        c[s2[j]+N]=j;    }    isort(l, b);    int nl=1, t, ans=0;    for(int i=1; i<=n; ++i) {        while(nl<=n && l[t=b[nl]]<=i) {            if(a[t]!=-1) {                add(t, t);            }            ++nl;        }        if(a[i]!=-1) {            ans=max(ans, getmx(r[i])-i+1);        }    }    printf("%d\n", ans);    return 0;}