区間和の最大値/最小値クエリ
問題
長さ$ Nの数列$ (A_1, A_2, \ldots, A_N)と、これに対する$ Q個の、以下のいずれかであるようなクエリが与えられる。
1 p x: $ A_pに$ xを代入する。
2 l r: $ \max\left\{ \sum_{k = i}^{j} A_k \middle| l \le i \le j \le r \right\}を答える。
クエリを順番に処理せよ。
解法
セグメント木を使うと解ける。
区間和の最小値について、左右の端に接しているかどうかで$ 4通りの値を持つ。
2つのノードを結合するとき、結合する側の端に接している区間は、相手のノードに含まれる区間と結合することができる。
code:.rs
// ac-library-rs の例
struct RangeMinSum;
impl Monoid for RangeMinSum {
// (両端に接している, 少なくとも左端に接している, 少なくとも右端に接している, 任意の) 区間の和の最小値
type S = (i64, i64, i64, i64);
fn binary_operation(&(la, ll, lr, ln): &Self::S, &(ra, rl, rr, rn): &Self::S) -> i64; 4 { let a = la.saturating_add(ra);
let l = a.min(ll).min(la.saturating_add(rl));
let r = a.min(rr).min(lr.saturating_add(ra));
let n = l.min(r).min(ln).min(rn).min(lr.saturating_add(rl));
(a, l, r, n)
}
fn identity() -> Self::S {
(INF, INF, INF, INF)
}
}