【MX-S7-T3】「SMOI-R2」Monotonic Queue 题解

· · 题解

我们注意到，题目给出的这个代码只会在尾部退队的时候才会把 c_i 统计到 sum 里面，并且会从 0 开始到 r 把所有元素遍历一遍，因此 r 可以决定哪些数可以被退掉。

但与此同时，我们还会注意到，l 可以让底部的一些元素提前出队，因此考虑维护一个单调栈，枚举 r，找最优的一个到栈顶的连续区段，使得用 r 去退栈时答案最优，因为如果设我要退的位置为 x，我可以用区间 [x,x] 直接把 x 之前的数全部从队首退掉而不加入 sum。

但特别的，如果当前枚举的这个 r 无法使得单调栈退栈，应当直接继承上一位的答案。

同时，我们还会发现，如果我要退掉单调栈中的数 x，那么在 x 上方出现过的所有数都会被计入 sum，因为用 l 退队是自下而上退的，x 一旦存在其上方的数也一定存在，故上方的数不是被更上方的数退掉就是被 r 退掉，而这都会计入贡献，因此每向单调栈中加入一个数 y，栈内所有答案都要加上一个对应的 c。

因此，我们需要维护单调栈内每一个元素的权值 a_i 以及从栈顶退到该元素时的 sum，还要能够二分找到自底到顶第一个权值 a_i<a_r，并查询区间的最大 sum，因此用线段树维护。

Code

#include<bits/stdc++.h>
/*
    注意到 sum 只有在尾部退队的时候才会被 + 到
    我们尝试模拟一下这个过程
    如果没有这个 l 就是在从左往右做单调栈过程中模拟一遍记录历史最大值就好了 
    但是有了 l 我们可以通过 l 来控制 一些位置不被加到 
    所以相当于 找到单调栈中最底部的位置 选择一个到栈顶的连续区段来 +
    然后正常单调栈删除末尾
    但是 要删除一个数 在这个数上方的数都一定被删了 所以要动态的把这些数的贡献弄进答案里 
    如果一个数都退不掉 那么我们同时记录一个 lasans 来表示上一次操作的答案 继承它即可
    因此我们需要一个数据结构实现以下操作：
    1.区间加 2.二分 3.区间覆盖 4.单点插入
    显然线段树 
*/
using LL=long long;
LL read()
{
    char ch=getchar();
    LL x=0;
    int f=0;
    while(ch<'0'||ch>'9')
        f=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
    return f?~x+1:x;
}
const int N=5e5+5;
const LL inf=1e18;
int n,a[N];
LL c[N];
struct node{
    int mnA,clr;
    LL val,plus;
    void add(LL x)
    {
        val+=x;
        plus+=x;
    }
    void clear()
    {
        clr=1;
        plus=val=mnA=0;
    }
};
#define lson rt<<1
#define rson rt<<1|1
node tree[N<<2];
void pushdown(int rt)
{
    if(tree[rt].clr)
    {
        tree[lson].clear();
        tree[rson].clear();
        tree[rt].clr=0;
    }
    if(tree[rt].plus)
    {
        tree[lson].add(tree[rt].plus);
        tree[rson].add(tree[rt].plus);
        tree[rt].plus=0;
    }
}
void update(int rt)
{
    tree[rt].mnA=std::min(tree[lson].mnA,tree[rson].mnA);
    tree[rt].val=std::max(tree[lson].val,tree[rson].val);
}
void add(int rt,int l,int r,int L,int R,LL x)
{
    if(l>R||r<L)
        return;
    if(L<=l&&r<=R)
    {
        tree[rt].add(x);
        return;
    }
    pushdown(rt);
    int mid=l+r>>1;
    add(lson,l,mid,L,R,x);
    add(rson,mid+1,r,L,R,x);
    update(rt);
}
void clear(int rt,int l,int r,int L,int R)
{
    if(l>R||r<L)
        return;
    if(L<=l&&r<=R)
    {
        tree[rt].clear();
        return;
    }
    pushdown(rt);
    int mid=l+r>>1;
    clear(lson,l,mid,L,R);
    clear(rson,mid+1,r,L,R);
    update(rt);
}
void insert(int rt,int l,int r,int Tar,int AA,LL V)
{
    if(l>Tar||r<Tar)
        return;
    if(l==r)
    {
        tree[rt].mnA=AA;
        tree[rt].val=V;
        return;
    }
    pushdown(rt);
    int mid=l+r>>1;
    insert(lson,l,mid,Tar,AA,V);
    insert(rson,mid+1,r,Tar,AA,V);
    update(rt);
}
int get_Lbound(int rt,int l,int r,int AA)
{
    if(tree[rt].mnA>AA)
        return -1;
    if(l==r)
        return l;
    int mid=l+r>>1;
    pushdown(rt);
    if(tree[lson].mnA<=AA)
        return get_Lbound(lson,l,mid,AA);
    else
        return get_Lbound(rson,mid+1,r,AA);
}
LL max(int rt,int l,int r,int L,int R)
{
    if(l>R||r<L)
        return -inf;
    if(L<=l&&r<=R)
        return tree[rt].val;
    pushdown(rt);
    int mid=l+r>>1;
    return std::max(max(lson,l,mid,L,R),max(rson,mid+1,r,L,R));
}
int top;
LL lasans,ans=-inf,tmp;
int main()
{
//  freopen("queue.in","r",stdin);
//  freopen("queue.out","w",stdout);
    n=read();
    for(int i=1;i<=n;++i)
        c[i]=read();
    for(int i=1;i<=n;++i)
        a[i]=read();
    for(int i=1;i<=n;++i)
    {
        int pos=get_Lbound(1,1,n,a[i]);
        if(pos>top)//单调栈内一个也退不掉 
            ++top;
        else//最少要吃到一位 不可能清空 
        {
            lasans=max(1,1,n,pos,top);
            clear(1,1,n,pos,top);
            top=pos;
        }
        ans=std::max(ans,lasans);
        insert(1,1,n,top,a[i],lasans);
        add(1,1,n,1,top,c[i]);
    }
    printf("%lld",ans);
}