POI2014 Salad Bar

Salad Bar

POI2014

题意

1.有一个长度为n的字符串，每一位只会是p或j。
2.找到一个子串S，使得不管是从左往右还是从右往左取，都保证每时每刻已取出的p的个数不小于j的个数。
3.求S的最大长度。

解

1.把p看做+1,把j看做-1

2.设 sum[i]为前缀和

3.如果区间[l,r]要作为答案，必须满足一下条件

条件1：sum[l]~sum[r]-sum[l-1]>=0 
(从左往右+1的个数总是不小于-1)
条件2：sum[r]-sum[r]~sum[l]>=0
(从右往左+1的个数总是不小于-1)

4.定义
ml[x]:x点向左第一个大于他的位置
mr[x]:x点向右第一个小于他的位置
单调栈预处理以上数组

5.枚举区间的左端点(左端点必须是p)，二分查找最远的右端点

设枚举的左端点为l
根据条件1，右端点的可选区间为[l,mr[l-1]-1]
(因为sum[mr[l]]是第一个小于sum[l-1]的数)

二分查找右端点时，
只要[mid,mr[l-1]-1]区间中存在一个mr[t]<l,就表示mid可行
（区间查询可以用ST表O(1)查询）

具体代码

#include<bits/stdc++.h>
using namespace std;
const int M=1000005;
char S[M];
int n,ans,sum[M],ml[M],mr[M];
int mi[M][20],Log[M];
void init(){
    Log[1]=0;
    for(int i=2;i<=n;i++)Log[i]=Log[i>>1]+1;
    for(int i=1;i<=n;i++){
        mi[i][0]=ml[i];
    }
    for(int j=1;j<20;j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
        }
    }
}
int query(int L,int R){
    int k=Log[R-L+1];
    return min(mi[L][k],mi[R-(1<<k)+1][k]);
}
bool check(int L,int R,int mid){
    return query(mid,R)<L;
}
int main() {
    scanf("%d %s",&n,S+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1];
        if(S[i]=='p')sum[i]++;
        else sum[i]--;
    }
    for(int i=n;i>=0;i--){
        int x=i+1;
        while(x<=n&&sum[x]>=sum[i])x=mr[x];
        mr[i]=x;
    }
    for(int i=1;i<=n;i++){
        int x=i-1;
        while(x>=1&&sum[x]<=sum[i])x=ml[x];
        ml[i]=x;
    }
    init();
    for(int i=1;i<=n;i++){
        if(S[i]=='j')continue;
        int L=i,R=mr[i-1]-1;
        while(L<=R){
            int mid=L+R>>1;
            if(check(i,mr[i-1]-1,mid)){
                L=mid+1;
                if(mid-i+1>ans){
                    ans=mid-i+1;
                }
            }else{
                R=mid-1;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}