セグメントツリーの高度な応用: 区間最小値更新と最大値・和の取得
Gorgeous Sequence: 区間最小値更新・区間最大値・区間和
長さ \(n\) の数列に対して次の操作をサポートする：
0 l r v: 区間 \([l, r]\) の要素を \(v\) との最小値で更新
1 l r: 区間の最大値を取得
2 l r: 区間の和を取得
各ノードで最大値・最大値の出現回数・二番目の最大値を管理。更新時：
\(mx \leq v\): 処理不要
\(smx < v < mx\): 最大値のみ更新
\(v ...
5月17日 01:21 投稿
CodeForces 258E - Little Elephant and Tree 木の部分木操作における複数解法
概要
本問題は複数の解法が存在する良問である。木の2頂点に対して各操作で部分木を合併するクエリが与えられる。各頂点について、自身を含む集合に一切に寄与していない（挿入回数が0の）頂点数を求める問題に帰着する。
問題構造の解析
各ノードに対して自分を祖先または子孫に含む操作回数を記録する。与えられた各クエリ \\( (a_i, b_i) \\) について、\\( subtree( ...
5月9日 14:34 投稿