给定一个01串S,求出它的一个尽可能长的子串S[i..j]，满足存在一个位置i<=x <j, S[i..x]中0比1多，而S[x + 1..j]中1比0多。求满足条件的最长子串长度。
收起
输入
一行包含一个只由0和1构成的字符串S。 S的长度不超过1000000。
输出
一行包含一个整数，表示满足要求的最长子串的长度。
输入样例
10
输出样例
0
分析：
我们把0看作-1，这样如果区间和>0，则区间0的个数大于1的个数；区间和<0,则区间1的个数大于0的个数。
首先，处理前缀和sum[i]，我们枚举每一个i，如果sum[i]>0,则左边可扩展的最大的区间长度l[i]为i;如果sum[i]<0,l[i]表示i到左边比sum[i]小的最左边的位置的区间长度。我们发现有一个最重要的特性：l[i]为sum[i]+1的位置,即第一个比它大的位置。sum[i]+1肯定比sum[i]+2,sum[i]+3.....的位置更优越。因为这是一个-1，1的串，经过2，肯定经过1.
对于右边的，后缀和
线段树
来自：https://blog.csdn.net/sunyutian1998/article/details/82926725
把0转为-1 问题就转为求最长的串 满足左负右正 对于每个前缀和pre[i] 看前面比它大的里面下标最小的 对于每个后缀和suf[i] 看后面比它小的里面下标最大的
#include <bits/stdc++.h>
using namespace std;const int N = 1000005;
int a[N],l[N],r[N],sum[N],suf[N];
int pos[N];
string s;
int main()
{cin>>s;int n=s.size();for(int i=1; i<=n; i++){if(s[i-1]=='0')a[i]=-1;elsea[i]=1;sum[i]=sum[i-1]+a[i];//cout<<a[i]<<endl;}memset(pos,-1,sizeof(pos));for(int i=1; i<=n; i++){if(sum[i]<0){l[i]=i;}else{if(pos[sum[i]+1]!=-1){l[i]=i-pos[sum[i]+1];}else{l[i]=0;pos[sum[i]]=i;}}}memset(pos,-1,sizeof(pos));for(int i=n; i>=1; i--){suf[i]=suf[i+1]+a[i];if(suf[i]>0){r[i]=n-i+1;}else{if(pos[-(suf[i]-1)]!=-1){r[i]=pos[-(suf[i]-1)]-i;}else{r[i]=0;pos[-(suf[i])]=i;}}}int ans=0;for(int i=1; i<n; i++){if(l[i]>0&&r[i+1]>0)ans=max(r[i+1]+l[i],ans);}cout<<max(0,ans)<<endl;return 0;
}
线段树：
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000010;
const int N=0x3f3f3f3f;int minn[4*maxn];
int ary[maxn],pre[maxn],suf[maxn],tmp[maxn],lef[maxn],rgt[maxn];
int n,len;
char ch[maxn];void update(int tar,int val,int l,int r,int cur)
{int m;minn[cur]=min(minn[cur],val);if(l==r) return;m=(l+r)/2;if(tar<=m) update(tar,val,l,m,2*cur);else update(tar,val,m+1,r,2*cur+1);
}int query(int pl,int pr,int l,int r,int cur)
{int res,m;if(pl<=l&&r<=pr) return minn[cur];res=N,m=(l+r)/2;if(pl<=m) res=min(res,query(pl,pr,l,m,2*cur));if(pr>m) res=min(res,query(pl,pr,m+1,r,2*cur+1));return res;
}int main()
{int i,res,ans,p;scanf("%s",ch);n=strlen(ch);for(i=0;i<n;i++){if(ch[i]=='0') ary[i+1]=-1;else ary[i+1]=1;}for(i=1;i<=n;i++){pre[i]=pre[i-1]+ary[i];tmp[i]=pre[i];}tmp[n+1]=0;sort(tmp+1,tmp+n+2);len=unique(tmp+1,tmp+n+2)-tmp-1;for(i=1;i<=n;i++) pre[i]=lower_bound(tmp+1,tmp+len+1,pre[i])-tmp;memset(minn,0x3f,sizeof(minn));memset(lef,-1,sizeof(lef));p=lower_bound(tmp+1,tmp+len+1,0)-tmp;update(p,0,1,len,1);for(i=1;i<=n;i++){update(pre[i],i,1,len,1);if(pre[i]+1<=len) res=query(pre[i]+1,len,1,len,1);else res=N;if(res!=N) lef[i]=res;}for(i=n;i>=1;i--){suf[i]=suf[i+1]+ary[i];tmp[i]=suf[i];}tmp[n+1]=0;sort(tmp+1,tmp+n+2);len=unique(tmp+1,tmp+n+2)-tmp-1;for(i=1;i<=n;i++) suf[i]=lower_bound(tmp+1,tmp+len+1,suf[i])-tmp;memset(minn,0x3f,sizeof(minn));memset(rgt,-1,sizeof(rgt));p=lower_bound(tmp+1,tmp+len+1,0)-tmp;update(p,-n-1,1,len,1);for(i=n;i>=1;i--){update(suf[i],-i,1,len,1);if(suf[i]-1>=1) res=query(1,suf[i]-1,1,len,1);else res=N;if(res!=N) rgt[i]=-res;}//for(i=1;i<=n;i++) printf("%d %d\n",lef[i],rgt[i]);ans=0;for(i=1;i+1<=n;i++){if(lef[i]!=-1&&rgt[i+1]!=-1) ans=max(ans,rgt[i+1]-lef[i]-1);}printf("%d\n",ans);return 0;
}