結果

問題 No.776 A Simple RMQ Problem
ユーザー kimiyuki
提出日時 2019-11-22 01:31:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 484 ms / 3,000 ms
コード長 4,459 bytes
コンパイル時間 2,532 ms
コンパイル使用メモリ 202,268 KB
最終ジャッジ日時 2025-01-08 04:26:01
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
/**
 * @brief a segment tree
 * @tparam Monoid (commutativity is not required)
 */
template <class Monoid>
struct segment_tree {
    typedef typename Monoid::value_type value_type;
    int n;
    std::vector<value_type> a;
    const Monoid mon;
    segment_tree() = default;
    segment_tree(int a_n, value_type initial_value = Monoid().unit(), Monoid const & a_mon = Monoid()) : mon(a_mon) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(2 * n - 1, mon.unit());
        std::fill(a.begin() + (n - 1), a.begin() + ((n - 1) + a_n), initial_value); // set initial values
        REP_R (i, n - 1) a[i] = mon.append(a[2 * i + 1], a[2 * i + 2]); // propagate initial values
    }
    void point_set(int i, value_type z) { // 0-based
        assert (0 <= i and i <= n);
        a[i + n - 1] = z;
        for (i = (i + n) / 2; i > 0; i /= 2) { // 1-based
            a[i - 1] = mon.append(a[2 * i - 1], a[2 * i]);
        }
    }
    value_type range_concat(int l, int r) { // 0-based, [l, r)
        assert (0 <= l and l <= r and r <= n);
        value_type lacc = mon.unit(), racc = mon.unit();
        for (l += n, r += n; l < r; l /= 2, r /= 2) { // 1-based loop, 2x faster than recursion
            if (l % 2 == 1) lacc = mon.append(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = mon.append(a[(-- r) - 1], racc);
        }
        return mon.append(lacc, racc);
    }
};
struct subinterval_max_sum_monoid {
    typedef struct {
        int64_t left, sum, right, max;
    } value_type;
    value_type unit() const {
        return (value_type) { 0ll, 0ll, 0ll, INT64_MIN };
    }
    value_type append(value_type a, value_type b) const {
        if (a.max == INT64_MIN) return b;
        if (b.max == INT64_MIN) return a;
        int64_t left = max(a.left, a.sum + b.left);
        int64_t sum = a.sum + b.sum;
        int64_t right = max(a.right + b.sum, b.right);
        int64_t max_ = max(left, max(sum, max(right, max(a.right + b.left, max(a.max, b.max)))));
        return (value_type) { left, sum, right, max_  };
    }
    static value_type make(int64_t a) {
        return (value_type) { a, a, a, a };
    }
    template <class SegmentTree>
    static int64_t calculate(SegmentTree & segtree, int l1, int l2, int r1, int r2) {
        // use [l, r] for l in [l1, l2) and r in [r1, r2)
        assert (l1 <= l2);  // [l1, l2)
        assert (r1 <= r2);  // [r1, r2)
        r1 = max(r1, l1);
        r2 = max(r2, l1);
        l1 = min(l1, r2);
        l2 = min(l2, r2);
        assert (l1 <= r1 and r1 <= r2);
        assert (l1 <= l2 and l2 <= r2);
        int64_t answer = INT64_MIN;
        if (r1 < l2) {
            answer = max(answer, segtree.range_concat(r1, l2).max);
            if (l1 <= r1 and r1 <= l2) {
                answer = max(answer, segtree.range_concat(l1, r1).right + segtree.range_concat(r1, min(l2, r2)).left);
            }
            if (r1 <= l2 and l2 <= r2) {
                answer = max(answer, segtree.range_concat(max(l1, r1), l2).right + segtree.range_concat(l2, r2).left);
            }
            swap(l2, r1);
        }
        answer = max(answer, segtree.range_concat(l1, l2).right + segtree.range_concat(l2, r1).sum + segtree.range_concat(r1, r2).left);
        return answer;
    }
};
int main() {
    // read the initial sequence
    int n, q; cin >> n >> q;
    vector<int64_t> a(n);
    REP (i, n) {
        cin >> a[i];
    }
    // construct a segment tree
    segment_tree<subinterval_max_sum_monoid> segtree(n);
    REP (i, n) {
        segtree.point_set(i, subinterval_max_sum_monoid::make(a[i]));
    }
    // handle queries
    while (q --) {
        string cmd; cin >> cmd;
        if (cmd == "set") {
            int i; int64_t x; cin >> i >> x;
            -- i;
            segtree.point_set(i, subinterval_max_sum_monoid::make(x));
        } else if (cmd == "max") {
            int l1, l2, r1, r2; cin >> l1 >> l2 >> r1 >> r2;  // [l1, l2], [r1, r2]
            -- l1;
            -- r1;
            cout << subinterval_max_sum_monoid::calculate<>(segtree, l1, l2, r1, r2) << endl;
        }
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0