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

· · 题解

找性质题。找到性质之后就是简单线段树优化 dp。

思路

据 @Abnormal123 赛时观察 1h 的结论：我们只选择长度为 1 的区间即可达到最优解。证明主要从能拿到可能的贡献区间和能不选可以避免的负贡献区间两方面考虑。

按小 L 的操作实现，我们先移动右端点，然后再移动左端点。考虑一段什么样的正贡献区间是可拿到的，如果该区间的最大值小于右端点的下一个值，那么显然是可以在右端点移动过程中获得所有贡献的。我们直接选择一个位于该区间右端点的长度为 1 的区间即可。

考虑什么样的负贡献区间可以避免，如果该区间严格单调不下降，那么所有元素都会存在队列里，可以通过移动左端点来 pop_back 掉它们。此时在区间右端点选择一个长度为 1 的区间可以实现。

至于那些不得不吃的负贡献，我们直接忽略掉即可，因为结果是不变的。

那么之后就可以用 dp 求解了。设 f_i 为钦定必须吃到 i 的贡献，即选 [i,i] 这一区间的最大值，容易写出转移式：f_i=\max_{j=0}^{i-1}f_j+val_{[j,i]}。val_{[j,i]} 表示 [j,i] 这段区间产生的贡献。

考虑这个 val 怎么求。我们发现一个点 i 若产生贡献，那么一定存在某一次右端点移动包含了 i 和它之后第一个大于它的数。我们记这个第一个大于 a_i 的数的下标为 nxt_i，这个求解的方法很多，树状数组或者单调队列均可。容易发现这个 nxt 值是单调不降的，所以我们将所有 nxt 值为 nxt_i 的下标装入 pre_{nxt_i} 中，每当遍历到一个点时，将 pre_{i} 中所有值取出计算贡献即可。

任意包含 [i,nxt_i] 这段区间的区间都会吃到 i 的贡献，这等价于对一个前缀做了一个区间加的操作。所以我们直接上线段树优化，就可以将转移的复杂度优化至 \mathcal{O(n\log n)} 的了。

实现

#include<bits/stdc++.h>
#define fo(x, y, z) for(int (x) = (y); (x) <= (z); (x)++)
#define fu(x, y, z) for(int (x) = (y); (x) >= (z); (x)--)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define lx ll
inline lx qr()
{
    char ch = getchar(); lx x = 0, f = 1;
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}
#undef lx
#define qr qr()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define ppp pair<pii, pii>
#define fi first
#define se second
#define M_P(x, y) make_pair(x, y)
#define P_B(x) push_back(x)
const int Ratio = 0;
const int N = 5e5 + 5;
const int mod = 998244353;
int n, m;
int a[N], c[N], t[N];
ll v[N << 2], lazy[N << 2], f[N];
vector<int> pre[N];
namespace Wisadel
{
    #define ls (rt << 1)
    #define rs (rt << 1 | 1)
    #define mid ((l + r) >> 1)
    inline void Wpushup(int rt){v[rt] = max(v[ls], v[rs]);}
    inline void Wpushdown(int rt)
    {
        v[ls] += lazy[rt], v[rs] += lazy[rt];
        lazy[ls] += lazy[rt], lazy[rs] += lazy[rt];
        lazy[rt] = 0;
    }
    inline void Wbuild(int rt, int l, int r)
    {
        if(l == r)
        {
            v[rt] = f[l];
            return ;
        }
        Wbuild(ls, l, mid), Wbuild(rs, mid + 1, r);
        Wpushup(rt);
    }
    inline void Wupd(int rt, int l, int r, int x, ll val)
    {
        if(l == r) return v[rt] = val, void();
        if(lazy[rt]) Wpushdown(rt);
        if(x <= mid) Wupd(ls, l, mid, x, val);
        else Wupd(rs, mid + 1, r, x, val);
        Wpushup(rt);
    }
    inline void Wupd(int rt, int l, int r, int x, int y, ll val)
    {
        if(x <= l && r <= y)
        {
            v[rt] += val, lazy[rt] += val;
            return ;
        }
        if(lazy[rt]) Wpushdown(rt);
        if(x <= mid) Wupd(ls, l, mid, x, y, val);
        if(y > mid) Wupd(rs, mid + 1, r, x, y, val);
        Wpushup(rt);
    }
    inline void Tm(int x, int v){for(; x <= n; x += (x & -x)) t[x] = min(t[x], v);}
    inline int Tq(int x){int res = 2e9; for(; x; x -= (x & -x)) res = min(res, t[x]); return res;}
    short main()
    {
        n = qr;
        fo(i, 1, n) c[i] = qr;
        fo(i, 1, n) a[i] = qr, t[i] = 2e9, f[i] = -2e18;
        fu(i, n, 1)
        {
            int zc = Tq(n - a[i] + 1);
            if(zc <= n) pre[zc].P_B(i);
            Tm(n - a[i] + 1, i);
        }
        Wbuild(1, 0, n);
        ll ans = -2e18;
        fo(i, 1, n)
        {
            for(auto j : pre[i])
                Wupd(1, 0, n, 0, j, c[j]);
            ans = max(ans, v[1]);
            Wupd(1, 0, n, i, v[1]);
        }
        printf("%lld\n", ans);
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
// All talk and never answer

完结撒花~