P9993 [Ynoi Easy Round 2024] TEST_133 题解

JiaY19 · 2023-12-26 11:31:46 · 题解

思路

看到时限这么大，考虑暴力做法。

我们将原序列分为 \text{B} 个块，每个块类似线段树三一样的维护 add,maxadd，表示这一块需要加的值，加的值的历史最大值。

同时对于每个数可以维护一个真实值与一个历史最值。

那么下传标记可以写成这样。

inline void push(int p)
{
    fro(i, L[p], R[p])
        sum[i] = max(sum[i], a[i] + madd[p]),
        a[i] = a[i] + add[p];
    add[p] = madd[p] = 0;
}

考虑所有数 \le x 的限制。

有一个很暴力的想法是，对于散块我们我们直接遍历，整块时二分解决问题。

那么对于每个块我们可以在开始构建与重构时进行排序维护。

inline void make(int p)
{
    iota(s + L[p], s + R[p] + 1, L[p]);
    sort(s + L[p], s + R[p] + 1, [&](int x, int y){
        return a[x] < a[y];
    });
    num[L[p]] = sum[s[L[p]]];
    fro(i, L[p] + 1, R[p]) num[i] = max(num[i - 1], sum[s[i]]);
    fro(i, L[p], R[p]) b[i] = a[s[i]];
}

其中，num 是前缀历史最大值的最值。

同样，在修改时，我们整块可以只维护标记，而散块需要下传重构。

inline void upd(int l, int r, int x)
{
    push(pos[l]);
    fro(i, l, r) a[i] = a[i] + x, sum[i] = max(sum[i], a[i]);
    make(pos[l]);
}
inline void change(int l, int r, int x)
{
    if(pos[l] == pos[r])
        return upd(l, r, x);
    upd(l, R[pos[l]], x);
    upd(L[pos[r]], r, x);
    fro(i, pos[l] + 1, pos[r] - 1)
        add[i] = add[i] + x,
        madd[i] = max(madd[i], add[i]);
}

这样，就在 O(n\sqrt{n}\log n) 的时间复杂度解决了这个题，40s 的时限下还是绰绰有余。

可能可以通过分散层叠做到严格根号，但是不需要了。

Code

AC记录。