题解：CF1787I Treasure Hunt

Claire0918 · 2025-10-03 22:06:04 · 题解

注意到该和式即求最大的 [1, q] 之和加上 [s, t] 之和使得 q \notin [s, t)。我们希望 q 与 s, t 无关，这样就是最大前缀和加上最大子段和（注意均可以取 0）。我们注意到当 [s, t] 取得最大子段和时，如果 q \in [s, t)，使 q = t 显然更优，于是最大前缀和的 q 一定不属于 [s, t)，直接考虑最大子段和加上最大前缀和即可。

我们考虑倒着加入数。设当前考虑了 [i + 1, n] 的后缀，[i + 1, j] 的最大前缀和为 p_j，最大子段和为 q_j。因为较大的 j 的答案严格包含较小的 j，所以 p_j, q_j 均单调不降。我们考量加入 i 后有怎样的变化。对于任意 j > i，显然有 p_j \gets \max\{p_j + a_i, a_i, 0\}，我们在线段树上将 [i + 1, n] 区间加 a_i，随后线段树上二分最小的小于 \max\{a_i, 0\} 的位置 x，将 [i, x] 区间赋值为 \max\{a_i, 0\} 即可。

我们记 l_j 表示 [i, j] 的最大子段和的左端点，s_i = \sum_{j = 1}^{i} a_j，显然 l_j 是单调不降的，s_{l_j} 是单调不升的。在加入 a_i 时，如果 s_{l_j} > s_i，那么我们将 l_j \gets i 显然不劣，而由单调性我们知道这样的 l_j 一定是一段区间，我们使用单调栈维护 s_{l_j} 即可。因为一些 q_j 增加了，所以对于一些 x > j，可能 q_j > q_x。因为 q_x 单调不降，满足该条件的 x 仍然是一段区间，我们考虑每个变化的 q_j，线段树上二分最大的 x 使 q_j > q_x，区间修改 [j + 1, x] 即可。同时，如果 q_j < \max\{0, a_i\}，我们将 q_j \gets \max\{0, a_i\} 不劣，而这样的 j 依然是一个区间，线段树上二分做区间覆盖即可。

综上，我们完整地解决了以上问题，时间复杂度 \mathcal{O}(n\log n)。注意本题稍微卡常。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))
#pragma GCC optimize ("Ofast")

using namespace std;

namespace IO{
    #define SIZ (1 << 18)
    char ibuf[SIZ], *p1 = nullptr, *p2 = nullptr;
    #define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZ, stdin), p1 == p2) ? EOF : *p1++)
    template <typename tp>
    void rd(tp &x){
        x = 0;
        int f = 1;
        char c = gc();
        for (;!isdigit(c); c == '-' && (f = -1), c = gc());
        for (;isdigit(c); x = x * 10 + (c ^ 48), c = gc());
        x *= f;
    }
    template <typename tp, typename... Arg>
    inline void rd(tp &x, Arg &...args){
        rd(x), rd(args...);
    }
    char obuf[SIZ], *p3 = obuf;
    inline void flush(){
        fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
    }
    inline void pc(const char c){
        p3 - obuf == SIZ && (flush(), 1538), *p3++ = c;
    }
    template <typename tp>
    void prt(tp x, char ed = '\n'){
        x < 0 && (pc('-'), x = -x);
        static char stk[40];
        int stkp = 0;
        do{
            stk[stkp] = char(x % 10), x /= 10, ++stkp;
        } while (x);
        while (stkp){
            pc(char(stk[--stkp] + '0'));
        }
        pc(ed);
    }
    #undef gc
    #undef SIZ
}

using namespace IO;

const int maxn = 1e6 + 5, mod = 998244353;

struct Val{
    int l, r;
    long long val;
    constexpr Val(int l = 0, int r = 0, long long val = 0): l(l), r(r), val(val){}
} stk[maxn];

int t, n, tot, res;
int a[maxn];
long long pre[maxn];
pair<int, int> tmp[maxn];

template<typename Tp_x, typename Tp_y>
inline int mod_add(Tp_x x, Tp_y y){
    return x += y, x >= mod ? x -= mod : x;
}

template<typename Tp_x, typename Tp_y>
inline int self_mod_add(Tp_x &x, Tp_y y){
    return x = mod_add(x, y);
}

template<typename Tp, typename... Arg>
inline int mod_add(Tp x, Arg ...args){
    return x += mod_add(args...), x >= mod ? x -= mod : x;
}

namespace segtree{
    struct{
        long long mn, modi, sum, add;
    } tree[maxn << 2];
    inline void pushup(int index){
        tree[index].sum = tree[index << 1].sum + tree[index << 1 | 1].sum, tree[index].mn = min(tree[index << 1].mn, tree[index << 1 | 1].mn);
    }
    inline void _modi(int index, int L, int R, long long k){
        tree[index].sum = (R - L + 1) * k, tree[index].mn = tree[index].modi = k, tree[index].add = 0;
    }
    inline void _add(int index, int L, int R, long long k){
        tree[index].sum += (R - L + 1) * k, tree[index].mn += k, tree[index].add += k;
    }
    inline void pushdown(int index, int L, int R){
        const int mid = L + R >> 1;
        tree[index].modi < 1e18 && (_modi(index << 1, L, mid, tree[index].modi), _modi(index << 1 | 1, mid + 1, R, tree[index].modi), tree[index].modi = 1e18);
        _add(index << 1, L, mid, tree[index].add), _add(index << 1 | 1, mid + 1, R, tree[index].add), tree[index].add = 0;
    }
    inline void modify(int index, int L, int R, int l, int r, long long k){
        if (l <= L && r >= R){
            return _modi(index, L, R, k);
        }
        pushdown(index, L, R);
        const int mid = L + R >> 1;
        l <= mid && (modify(index << 1, L, mid, l, r, k), 1538), r > mid && (modify(index << 1 | 1, mid + 1, R, l, r, k), 1538), pushup(index);
    }
    inline void add(int index, int L, int R, int l, int r, long long k){
        if (l <= L && r >= R){
            return _add(index, L, R, k);
        }
        pushdown(index, L, R);
        const int mid = L + R >> 1;
        l <= mid && (add(index << 1, L, mid, l, r, k), 1538), r > mid && (add(index << 1 | 1, mid + 1, R, l, r, k), 1538), pushup(index);
    }
    inline long long query(int index, int L, int R, int l, int r){
        if (l <= L && r >= R){
            return tree[index].sum;
        }
        pushdown(index, L, R);
        const int mid = L + R >> 1;
        long long res = 0;
        l <= mid && (res += query(index << 1, L, mid, l, r)), r > mid && (res += query(index << 1 | 1, mid + 1, R, l, r));
        return res;
    }
    inline int fnd(int index, int L, int R, long long x){
        if (L == R){
            return L;
        }
        pushdown(index, L, R);
        const int mid = L + R >> 1;
        return tree[index << 1 | 1].mn <= x ? fnd(index << 1 | 1, mid + 1, R, x) : fnd(index << 1, L, mid, x);
    }
}

using namespace segtree;

int main(){
    rd(t);
    while (t--){
        rd(n), tot = res = 0;
        for (int i = 1; i <= n << 2; i++){
            tree[i].sum = tree[i].add = 0, tree[i].mn = -1e18, tree[i].modi = 1e18;
        }
        for (int i = 1; i <= n; i++){
            rd(a[i]), pre[i] = pre[i - 1] + a[i];
        }
        for (int i = n; i; i--){
            int top = 0;
            while (tot && stk[tot].val > pre[i - 1]){
                add(1, 1, n, stk[tot].l, stk[tot].r, stk[tot].val - pre[i - 1]), tmp[++top] = make_pair(stk[tot].l, stk[tot].r), tot--;
            }
            int L = n, R = 0;
            for (int j = top; j; j--){
                const long long l = tmp[j].first, r = tmp[j].second, v = query(1, 1, n, r, r), pos = fnd(1, 1, n, v);
                pos > r && (modify(1, 1, n, r + 1, pos, v), 1538), L = min(L, int(l)), R = max(R, int(pos));
            }
            const int pos = fnd(1, 1, n, max(0, a[i]));
            modify(1, 1, n, i, pos, max(0, a[i])), L = min(L, i), R = max(R, pos);
            if (L <= R){
                for (;tot && stk[tot].r <= R; tot--);
                tot && (stk[tot].l = max(stk[tot].l, R + 1)), stk[++tot] = Val(L, R, pre[i - 1]);
            }
            self_mod_add(res, (query(1, 1, n, i, n) % mod + mod) % mod);
        }
        for (int i = 1; i <= n << 2; i++){
            tree[i].sum = tree[i].add = 0, tree[i].mn = -1e18, tree[i].modi = 1e18;
        }
        for (int i = n; i; i--){
            i < n && (add(1, 1, n, i + 1, n, a[i]), 1538);
            const int pos = fnd(1, 1, n, max(0, a[i]));
            modify(1, 1, n, i, pos, max(0, a[i])), self_mod_add(res, (query(1, 1, n, i, n) % mod + mod) % mod);
        }
        prt(res);
    }
    flush();

return 0;
}