A Simple RMQ Problem [yukicoder No.776] - はまやんはまやんはまやん

前提知識

特殊なマージをするセグメント木

解説

実装をする。
セグメントツリーに複数要素をもたせるパターンがある。
セグメントツリーの各頂点には以下の要素をもたせる。
区間[L,R]について、
　sm := 区間和
　lft := 左から1個以上の要素を選んだときの総和の最大
　ght := 右から1個以上の要素を選んだときの総和の最大
　opt := 区間の中での連続区間のうちの総和の最大
を保持して、更新する。
更新式は以下の様にする。

    res.sm = x.sm + y.sm;
    res.lft = max({ x.lft, x.sm + y.lft, x.sm });
    res.rht = max({ y.rht, x.rht + y.sm, y.sm });
    res.opt = max({ x.opt, y.opt, x.rht + y.lft, x.rht, x.lft, y.rht, y.lft });

xが結合前の左の要素、yが結合前の右の要素。
　
このデータ構造を使うと、答えが出せる。
setの場合は普通に更新する。
maxの場合を解説する。
L[a,b]とR[c,d]とした場合に、
cが[a,b]より左側にあっても、選ばれることはないので、c=max(c,a)とする。
bが[c,d]より右側にあっても、選ばれることはないので、b=min(b,d)とする。
このように変形後すると、区間を並べたときに左がL, 右がRとなる。
ここから、2通りに場合分けする。
　
b＜cのとき。これはかぶっている区間が無い場合である。
こうすると、左端が[a,b]にあり、(b,c)の区間は必ず使われて、右端が[c,d]にある。
左端では右側からの最大値を使い、右端では左側からの最大値を使う。
　
そうでない場合。これはかぶっている区間がある場合である。
ここは更に3通りに場合分けできる。
① 左端と右端がどちらもかぶっている区間にある
この状態の答えはかぶっている区間のoptになる。
② 左端が[a,c)の区間にあり、右端が[c,d]の区間にある
[a,c)では右側からの最大値、[c,d]では左側からの最大値を取った和が答え。
③ 左端が[a,b]にあり、右端が(b,d]の区間にある
[a,b]では右側からの最大値、(b,d]では左側からの最大値を取った和が答え。
①②③で被っているものがあるが、最大値を取っているので、問題ない。
これで答えられる。

struct func {
    ll sm, lft, rht, opt;
    func(ll a = infl, ll b = 0, ll c = 0, ll d = 0) : sm(a), lft(b), rht(c), opt(d) {}
};
func operator*(func x, func y) {
    func res;

    if (x.sm == infl) return y;
    if (y.sm == infl) return x;

    res.sm = x.sm + y.sm;
    res.lft = max({ x.lft, x.sm + y.lft, x.sm });
    res.rht = max({ y.rht, x.rht + y.sm, y.sm });
    res.opt = max({ x.opt, y.opt, x.rht + y.lft, x.rht, x.lft, y.rht, y.lft });

    return res;
}
//---------------------------------------------------------------------------------------------------
int N, Q, A[101010];
SegTree<func, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void upd(int i, ll v) {
    st.update(i, func(v, v, v, v));
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) {
        cin >> A[i];
        upd(i, A[i]);
    }
    rep(q, 0, Q) {
        string s; cin >> s;
        if (s == "set") {
            int i, x; cin >> i >> x; i--;
            upd(i, x);
        } else {
            int a, b, c, d; cin >> a >> b >> c >> d;
            a--; b--; c--; d--;

            c = max(c, a);
            b = min(b, d);

            ll ans = -infl;
            if (b < c) {
                ans = 0;
                ans += st.get(a, b + 1).rht;
                if(b + 1 < c) ans += st.get(b + 1, c).sm;
                ans += st.get(c, d + 1).lft;
            } else {
                if(c < b + 1) chmax(ans, st.get(c, b + 1).opt);
                if(a < c and c < d + 1) chmax(ans, st.get(a, c).rht + st.get(c, d + 1).lft);
                if(a < b + 1 and b + 1 < d + 1) chmax(ans, st.get(a, b + 1).rht + st.get(b + 1, d + 1).lft);
            }
            printf("%lld\n", ans);
        }
    }
}