P3564 [POI2014] BAR-Salad Bar 题解

· · 题解

写在前面

前置芝士：线段树，st 表。

这个写法略有点奇怪且有点卡空间，注意实现。

算法分析

把 p 看成 1，j 看成 -1，那么题目要求我们找到一个最长的区间满足它的所有前缀和和后缀和都非负。

考虑枚举右端点，记 suf_i 表示第 i 位的后缀和，也就是说，如果区级 [l,r] 合法，那么必然有：

\forall i \in [l,r],suf_i-suf_{r+1}\ge 0

这条式子也可以这么写：

\min\{suf_i\}\ge suf_{r+1},i\in [l,r]

显然左端点是可以二分的，我们可以用一个 st 表去维护区间 suf_i 的最小值，二分找左端点，这样我们就找到了答案可能在的区间。

接下来我们需要考虑如何满足前缀和的限制。

我们可以这样认为：最开始所有的点都有可能是答案，每次向右延长一位，可能会导致从某些点开始的前缀和小于 0，这个时候这个点就不再是答案了，把它封掉。最后我们只需要找到指定范围内最左边那个点就可以了。

注意到上述过程我们需要实现这么几个操作：查询某个区间内第一个符合条件的点，封点和区间加。注意到每一个点一旦被封上就不可能作为答案，所以我们可以参考势能线段树的写法，维护一个区间最小值，在区间加的时候如果发现这个区间存在点前缀和小于 0，那么就暴力打开这个区间封点，以后不再访问这个点，也不会以这个点作为答案。封锁单个点的时间复杂度是 O(\log n)，每个点最多被封锁一次，所以封点的总时间复杂度是 O(n\log n) 的。

st 表查询 O(n\log n)，线段树维护和查询 O(n\log n)，总时间复杂度 O(n\log n)。

Code

实现时注意空间，有点卡。

#include<bits/stdc++.h>
#define ls(rt) tree[rt].lson
#define rs(rt) tree[rt].rson
const int N=1e6+5,inf=1e9;
struct node{
    int mn,fst,lson,rson;
    int plus;
    void upd(int x)//全体加减并不改变相对大小
    {
        mn+=x;
        plus+=x;
    }
};
node tree[N<<1];
int pcnt=1;
void update(int rt)
{
    tree[rt].mn=std::min(tree[ls(rt)].mn,tree[rs(rt)].mn);
    tree[rt].fst=std::min(tree[ls(rt)].fst,tree[rs(rt)].fst);
}
void pushdown(int rt)
{
    if(!tree[rt].plus)
        return;
    if(tree[ls(rt)].mn==inf)
        tree[ls(rt)].upd(tree[rt].plus);
    if(tree[rs(rt)].mn==inf)
        tree[rs(rt)].upd(tree[rt].plus);
    tree[rt].plus=0;
}
void build(int rt,int l,int r)
{
    if(l==r)
    {
        tree[rt].fst=l;
        return;
    }
    int mid=l+r>>1;
    ls(rt)=++pcnt;
    rs(rt)=++pcnt;
    build(ls(rt),l,mid);
    build(rs(rt),mid+1,r);
    update(rt);
}
void add(int rt,int l,int r,int L,int R,int x)
{
    if(l>R||r<L||tree[rt].mn==inf)//不会访问已经被封锁的点
        return;
    if(l==r)
    {
        tree[rt].upd(x);
        if(tree[rt].mn<0)//暴力封点
            tree[rt].mn=tree[rt].fst=inf;
        return;
    }
    if(L<=l&&r<=R&&tree[rt].mn+x>=0)
    {
        tree[rt].upd(x);
        return;
    }
    pushdown(rt);
    int mid=l+r>>1;
    add(ls(rt),l,mid,L,R,x);
    add(rs(rt),mid+1,r,L,R,x);
    update(rt);
}
int query(int rt,int l,int r,int L,int R)//查询左端点
{
    if(l>R||r<L||tree[rt].fst==inf)
        return inf;
    if(L<=l&&r<=R)
        return tree[rt].fst;
    pushdown(rt);
    int mid=l+r>>1;
    int resL=query(ls(rt),l,mid,L,R);
    int resR=query(rs(rt),mid+1,r,L,R);
    return std::min(resL,resR);
}
int st[N][20];
int n,ans;
char s[N];
int Log2(int x)
{
    int res=0;
    for(;(1<<res+1)<=x;++res);
    return res;     
}
int get_min(int L,int R)
{
    int len=R-L+1;
    int LOG=Log2(len);
    return std::min(st[L][LOG],st[R-(1<<LOG)+1][LOG]);
}
int find(int R)//找到合法的左端点区间
{
    int l=1,r=R,mid,res=R+1;
    while(l<=r)
    {
        mid=l+r>>1;
        if(get_min(mid,R)>=st[R+1][0])
        {
            res=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    return res;
}
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=n;i;--i)
        st[i][0]=st[i+1][0]+(s[i]=='p'?1:-1);
    for(int p=1;(1<<p)<=n;++p)
    {
        for(int i=1;i+(1<<p)-1<=n;++i)
            st[i][p]=std::min(st[i][p-1],st[i+(1<<p-1)][p-1]);
    }
    //预处理后缀和 st 表
    build(1,1,n);
    //完成初始化
    for(int i=1;i<=n;++i)
    {
        add(1,1,n,1,i,(s[i]=='p'?1:-1));
        if(s[i]=='j')
            continue;
        int P=find(i);
        int tmp=query(1,1,n,P,i);
        if(tmp<=i)
            ans=std::max(ans,i-tmp+1);
    }
    printf("%d",ans);
}