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

· · 题解

怎么大家都是 dp，来一个贪心（？）题解。

题意

有点复杂，自己看题面。

最终 sum 是所有通过右边弹出的元素的 c 的和。

思路

下文中，称 deque 的 front 为左边/前面。

观察题面中的代码，发现其实不需要管具体的 l_i,r_i，而是可以理解为有若干次操作，每次让 r\gets r+1 或 l\gets l+1，要求 l\leq r，然后做单调栈的 push_back（可能带有 pop_back） 或者 pop_front。

再做转化，变成选择一个 1\leq p \leq n，指定一组不降的 a_{1\sim p}，然后重复 p 次，每次令 r\gets r+1，然后令 l\gets a_r。这里的 l\gets l+1 和 r\gets r+1 同样也做单调栈操作。

先考虑如何算 a_i=1 的贡献。发现这样的话没有 pop_front 操作，直接做一遍单调栈即可，答案是每个前缀的 \max。

然后观察 pop_front 操作起到了什么作用。发现它相当于每次 push 完后，删去单调栈的一个前缀（不能删空）。那么我们可以直接把这个操作放到 push 操作的弹栈过程中，每次从后面弹出时（除了每轮弹出的第一个元素，这是因为不能删空），你可以放弃这次弹出，改为直接把栈删空。

此后由于不存在 pop_front 操作，直接称 pop_back 为弹出。

之后我们可以开始贪了。每次弹出一个元素（设之为 x）的时候，如果 c_x 非负，我们直接弹出它一定不亏。否则 c_x 是负的，此时如果我们只弹出 x 肯定时亏的，我们选择弹出它只可能因为在未来的某一时刻（不一定是这一次 r\gets r+1 导致的弹出）还要弹出此时的单调栈更左的元素，也就一定会弹出前一个元素（设之为 y，如果不存在 y 那么弹 x 肯定亏）。那么我们可以直接令 c_y\gets c_y+c_x，意思是如果需要弹出 y，那么弹出 x，否则不弹出 x。在不弹出 y 的情况下，不弹出 x 和删空栈是等价的，所以这样写和原问题是等价的。

模拟这个过程即可。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c[500005],ans,a[500005],s;
deque<int>q;//用 stack 就行了 
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%lld",&c[i]);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        int op=0;
        while(q.size()&&a[q.back()]<a[i]){
            int x=q.back();
            q.pop_back(); 
            if(op){
                if(c[x]>0) s+=c[x];//一定赚
                else if(q.size()) c[q.back()]+=c[x];//如果弹出 q.back()，那么弹出 x，否则清空。 
            }
            else s+=c[x],op=1;// 这是第一次弹出 
        }
        q.push_back(i);
        ans=max(ans,s);
    }
    cout<<ans;
}