結果

問題 No.2950 Max Min Product
ユーザー zawakasuzawakasu
提出日時 2024-10-28 13:17:33
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,561 ms / 3,000 ms
コード長 5,738 bytes
コンパイル時間 1,420 ms
コンパイル使用メモリ 91,396 KB
実行使用メモリ 31,048 KB
最終ジャッジ日時 2024-10-28 13:18:25
合計ジャッジ時間 50,645 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <utility>
#include <optional>
#include <cassert>
#include <stack>

const long long MOD{998244353};

long long norm(long long v) {
    return (v + MOD) % MOD;
}

long long add(long long L, long long R) {
    long long res{norm(L) + norm(R)};
    if (res >= MOD) res -= MOD;
    return res;
}

long long mult(long long L, long long R) {
    return (norm(L) * norm(R)) % MOD;
}
struct VD {
    long long max_sum{}, min_sum{}, prod_sum{};
    int len{};
    VD() = default;
    VD(long long mx, long long mn, long long pr, int l)
        : max_sum{mx}, min_sum{mn}, prod_sum{pr}, len{l} {}
};

struct VM {
    using T = VD;
    static T identity() {
        return VD{};
    }
    static T operation(T L, T R) {
        L.max_sum = add(L.max_sum, R.max_sum);
        L.min_sum = add(L.min_sum, R.min_sum);
        L.prod_sum = add(L.prod_sum, R.prod_sum);
        L.len += R.len;
        return L;
    }
};

struct OM {
    using T = std::pair<std::optional<int>, std::optional<int>>;
    static T identity() {
        return T{ std::nullopt, std::nullopt };
    }
    static T operation(T L, T R) {
        if (R.first) L.first = R.first;
        if (R.second) L.second = R.second;
        return L;
    }
};

VM::T mapping(VM::T v, OM::T o) {
    if (o.first and o.second) {
        v.max_sum = mult(*o.first, v.len);
        v.min_sum = mult(*o.second, v.len);
        v.prod_sum = mult(*o.first, mult(*o.second, v.len));
    }
    else if (o.first) {
        v.max_sum = mult(*o.first, v.len);
        v.prod_sum = mult(*o.first, v.min_sum);
    }
    else if (o.second) {
        v.min_sum = mult(*o.second, v.len);
        v.prod_sum = mult(*o.second, v.max_sum);
    }
    return v;
}

struct LazySegmentTree {
    using V = VM::T;
    using O = OM::T;
    static int parent(int v) {
        return v >>= 1;
    }
    static int left(int v) {
        return v << 1;
    }
    static int right(int v) {
        return v << 1 | 1;
    }
    static int depth(int v) {
        return 31 - __builtin_clz(v);
    }
    static int trailingZeros(int v) {
        return __builtin_ctz(v);
    }

    struct Node {
        V v{VM::identity()};
        O o{OM::identity()};
    };

    int n{};
    std::vector<Node> dat;
    static V action(const Node& node) {
        return mapping(node.v, node.o);
    }
    void propagate(int v) {
        dat[left(v)].o = OM::operation(dat[left(v)].o, dat[v].o);
        dat[right(v)].o = OM::operation(dat[right(v)].o, dat[v].o);
        dat[v].o = OM::identity();
    }
    void propagateAncestor(int v) {
        int dep{depth(v)};
        int zeros{trailingZeros(v)};
        for (int d{dep} ; d != zeros ; d--) {
            propagate(v >> d);
        }
    }
    void recalc(int v) {
        dat[v].v = VM::operation(action(dat[left(v)]), action(dat[right(v)]));
    }
    void recalcAncestor(int v) {
        v >>= trailingZeros(v);
        for (v = parent(v) ; v ; v = parent(v)) {
            recalc(v);
        }
    }
    LazySegmentTree() = default;
    LazySegmentTree(const std::vector<V>& A) : n{(int)A.size()}, dat(A.size() << 1) {
        assert(A.size());
        for (int i{} ; i < n ; i++) dat[i + n].v = A[i];
        for (int i{n} ; --i ; ) {
            dat[i].v = VM::operation(dat[left(i)].v, dat[right(i)].v);
        }
    }
    int size() const {
        return n;
    }
    void operation(int L, int R, const O& o) {
        assert(0 <= L and L <= R and R <= n);
        L += size();
        R += size();
        propagateAncestor(L);
        propagateAncestor(R);
        for (int l{L}, r{R} ; l < r ; l = parent(l), r = parent(r)) {
            if (l & 1) {
                dat[l].o = OM::operation(dat[l].o, o);
                l++;
            }
            if (r & 1) {
                r--;
                dat[r].o = OM::operation(dat[r].o, o); 
            }
        }
        recalcAncestor(L);
        recalcAncestor(R);
    }
    V product(int L, int R) {
        assert(0 <= L and L <= R and R <= n);
        L += size();
        R += size();
        propagateAncestor(L);
        propagateAncestor(R);
        recalcAncestor(L);
        recalcAncestor(R);
        V l{VM::identity()}, r{VM::identity()};
        for ( ; L < R ; L = parent(L), R = parent(R)) {
            if (L & 1) {
                l = VM::operation(l, action(dat[L]));
                L++;
            }
            if (R & 1) {
                R--;
                r = VM::operation(action(dat[R]), r);
            }
        }
        return VM::operation(l, r);
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N;
    std::cin >> N;
    std::vector<int> A(N);
    std::vector<VM::T> init(N);
    for (int i{} ; i < N ; i++) {
        int a;
        std::cin >> a;
        A[i] = a;
        init[i] = VM::T{a, a, (long long)a * a, 1};
    }
    std::vector<int> prevmax(N, -1), prevmin(N, -1);
    {
        std::stack<int> stack;
        for (int i{} ; i < N ; i++) {
            while (stack.size() and A[stack.top()] < A[i]) stack.pop();
            prevmax[i] = stack.size() ? stack.top() : -1;
            stack.push(i);
        }
    }
    {
        std::stack<int> stack;
        for (int i{} ; i < N ; i++) {
            while (stack.size() and A[stack.top()] > A[i]) stack.pop();
            prevmin[i] = stack.size() ? stack.top() : -1;
            stack.push(i);
        }
    }
    LazySegmentTree seg{init};
    long long ans{};
    for (int i{} ; i < N ; i++) {
        seg.operation(prevmax[i] + 1, i, OM::T{ A[i], std::nullopt }); 
        seg.operation(prevmin[i] + 1, i, OM::T{ std::nullopt, A[i] }); 
        ans = add(ans, seg.product(0, i + 1).prod_sum);
    }
    std::cout << ans << '\n';
}
0