frankchenfu 的博客

frankchenfu 的博客

题解 CF573B 【Bear and Blocks】

posted on 2018-02-16 17:16:18 | under 题解 |

这道题听说可以采用曼哈顿最小生成树的$\Theta(n \log_2n)$算法,不过这里不讨论。我们来讲一下如何使用线段树维护。


读完题目之后,我们很容易发现,最后消失的那几个方块至少有一个一定位于最底层(因为它上面的方块一定不会比它后消除)。所以我们设每个“塔”的高度为$h_i$,那么我们会发现第一次操作的时候它的高度就是$\min(h_i-1,h_{i-1},h_{i+1})$。不过因为 这个转移它有后效性,不能直接DP/递推得出答案。所以我们考虑如下递推式:我们递推第$k$次在第$i$座“塔”上操作后的高度,则$$h_i=\max(0,\displaystyle\min_{j=0}^{i}\{\min(h_{i-j},h_{i+j})-(k-j)\})$$

我们发现这个式子需要枚举$i$和$j$,复杂度不符合要求,怎么办呢?

观察发现,我们这里因为$k$是一个常数,不影响最优性;也就是说,我们要求的是$\displaystyle\min_{j=0}^{i}\{h_{i-j}+j\}$和$\displaystyle\min_{j=0}^{i}\{h_{i+j}+j\}$,也就是两个区间最值。于是,我们就使用线段树维护这个东西。


这样,我们就在$O(n\log_2n)$的时间内完成了递推,最后对于每一个$i$,我们就可以求出把这堆删除的最小时间。我们把答案取$\max$即可。代码如下:

#include<cstdio>
#include<cstring>

int min(int x,int y)
{
    return x<y?x:y;
}
int max(int x,int y)
{
    return x>y?x:y;
}

class seg_tree
{
    private:
        static const int MAXN=100010;
        struct node
        {
            int l,r,val;
            int lazy;
        }tree[MAXN<<2];
        void upd(int o)
        {
            tree[o].val=min(tree[o<<1].val,tree[o<<1|1].val);
        }
        void pushdown(int o)
        {
            int tmp=tree[o].lazy;
            tree[o].lazy=0;
            if(tmp)
            {
                tree[o<<1].lazy+=tmp;
                tree[o<<1|1].lazy+=tmp;
                tree[o<<1].val+=tmp;
                tree[o<<1|1].val+=tmp;
            }
        }

    public:
        int ord[MAXN];
        void build(int o,int l,int r)
        {
            tree[o].l=l;
            tree[o].r=r;
            tree[o].lazy=0;
            int mid=(l+r)>>1;
            if(l==r) 
            {
                tree[o].val=ord[l];
                return;
            }
            build(o<<1,l,mid);
            build(o<<1|1,mid+1,r);
            upd(o);
        }
        void update(int o,int lt,int rt,int v)
        {
            int l=tree[o].l,r=tree[o].r;
            int mid=(l+r)>>1;
            if(lt<=l&&r<=rt)
            {
                tree[o].val+=v;
                tree[o].lazy+=v;
                return;
            }
            pushdown(o);
            if(lt<=mid&&rt>=l) 
                update(o<<1,lt,rt,v);
            if(lt<=r&&rt>mid)
                update(o<<1|1,lt,rt,v);
            upd(o);
        }
        int query(int o,int lt,int rt)
        {
            int l=tree[o].l,r=tree[o].r;
            int mid=(l+r)>>1;
            if(lt<=l&&r<=rt)
                return tree[o].val;
            pushdown(o);
            int res=2147483647;
            if(lt<=mid&&rt>=l) 
                res=min(res,query(o<<1,lt,rt));
            if(lt<=r&&rt>mid)
                res=min(res,query(o<<1|1,lt,rt));
            return res;
        }
};
seg_tree sol;
int lans[100010],rans[100010];

int read()
{
    int res=0;char ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        res=(res<<3)+(res<<1)+ch-'0';
        ch=getchar();
    }
    return res;
}

int main()
{
    int n=read();;
    for(int i=1;i<=n;i++)
        sol.ord[i]=read();
    sol.build(1,0,n+1);
    for(int i=1;i<=n;i++)
    {
        sol.update(1,0,i-1,1);
        lans[i]=sol.query(1,0,i);
    }
    sol.build(1,0,n+1);
    for(int i=n;i;i--)
    {
        sol.update(1,i+1,n+1,1);
        rans[i]=sol.query(1,i,n+1);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        ans=max(ans,min(lans[i],rans[i]));
    printf("%d\n",ans);
    return 0;
}