POI2014 Salad Bar

这道题的大意就是给你一个字符串,里面只含有p和j,求一个最长的子串,使得从左边开始,p的个数一直比j多,从右边开始也一样.

这道题的话,一开始想歪了,就先对每个字符,算出来以它为起点往右最多能在哪里,然后再算出来以它为起点往左最多能走到哪里,这样的话,一个满足条件的子串一定满足$R[l]>=r,L[r]<=l$,然后按照左边小的排一下序,然后就可以乱搞一下了…

就是从左往右,每到一个点就把能够穿过它的都加入到现在已有的点集中,然后在把这个点右端点以内的最右的一个找到,这就是以这个点为左端点,能够得到的最长子串了.

具体的操作的话,使用树状数组来完成的,比较麻烦吧…

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1000005
using namespace std;
char A[M];
int sum[M],n;
struct Bit{
    int Tree[M<<1];
    void Pl(){
        memset(Tree,-1,sizeof(Tree));
    }
    void Add(int x,int v){
        while(x<=M<<1){
            if(v>Tree[x])Tree[x]=v;
            x+=x&(-x);
        }
    }
    int Qu(int x){
        int re=-1;
        while(x){
            if(Tree[x]>re)re=Tree[x];
            x-=x&(-x);
        }
        return re;
    }
}T;
struct W{
    int L,R,id;
    bool operator <(const W &a)const{
        return L<a.L;
    }
}Q[M];
int L[M],R[M];
int main(){
    scanf("%d %s",&n,A+1);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+(A[i]=='j'?-1:1);
    T.Pl();
    for(int i=n;i>=1;i--){
        Q[i].R=T.Qu(sum[i-1]+M-1);
        if(A[i]=='j')Q[i].R=-1;
        else if(Q[i].R!=-1)Q[i].R=n-Q[i].R+1;
        else if(Q[i].R==-1)Q[i].R=n;
        T.Add(sum[i]+M,n-i+1);R[i]=Q[i].R;
    }
    T.Pl();
    for(int i=n;i>=1;i--)sum[i]=sum[i+1]+(A[i]=='j'?-1:1);
    for(int i=1;i<=n;i++){
        Q[i].L=T.Qu(sum[i+1]+M-1);
        if(A[i]=='j')Q[i].L=-1;
        else if(Q[i].L==-1)Q[i].L=1;
        else Q[i].L++;
        T.Add(sum[i]+M,i);L[i]=Q[i].L;
    }
    for(int i=1;i<=n;i++)Q[i].id=i;
    T.Pl();
    sort(Q+1,Q+n+1);
    int ans=0,pos=1;
    while(pos<=n&&Q[pos].L==-1)pos++;
    for(int i=1;i<=n;i++){
        while(pos<=n&&Q[pos].L<=i)T.Add(Q[pos].id,Q[pos].id),pos++;
        if(R[i]!=-1){
            int tmp=T.Qu(R[i]);
            if(tmp!=-1&&tmp-i+1>ans)ans=tmp-i+1;
        }
    }
    printf("%d\n",ans);
    return 0;
}

改变一下前缀和,令p=1,j=-1,这样可以得到一个前缀和数组sum.

然后再继续考虑,我们可以发现,对于一个合法的区间[l,r],一定会有

$$sum[l]<=sum[i]<=sum[r],l<=i<=r$$
而这个前缀和又是连续的(每次都只会变化1),所以可以 $O(n)$地处理出每一个点下一个前缀和与它相等的点在哪里,放在nxt数组里面.

然后定义pev[i]为从i开始,最远的满足条件的字符的下标.

那么就可以解答问题了,每一次记录下上一次的pev,记为pre,然后再比较一下nxt[i-1]与pre哪一个更好,然后更新就行了.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 1000005
using namespace std;
char A[M];
int sum[M],nxt[M],pev[M];
int last[M];
int main(){
    int n,mi=0;scanf("%d %s",&n,A+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+(A[i]=='p'?1:-1);
        if(sum[i]<mi)mi=sum[i];
    }
    memset(last,-1,sizeof(last));
    for(int i=n,x;i>=0;i--){
        x=sum[i]-mi;
        nxt[i]=last[x];
        last[x]=i;
        pev[i]=i;
    }
    int ans=0;
    for(int i=n,pre=n;i>=1;i--){
        if(A[i]=='p'){
            if(~nxt[i-1]&&sum[pev[nxt[i-1]]]>=sum[pre])pre=pev[nxt[i-1]];
            pev[i-1]=pre;
            int ll=pre-i+1;
            if(ll>ans)ans=ll;
        }else pre=i-1;
    }
    printf("%d\n",ans);
    return 0;
}