はじめに
この記事では以下の遅延セグメント木をACLで実装する時のチートシートを示します。
言語はPythonです。
ACLについて
AtCoderのジャッジで使用可能な、競プロでよく使うテクニックがまとまったライブラリです。
導入はREADME.mdを参考にしてください。
区間加算・区間最小値
from atcoder.lazysegtree import LazySegTree
def op(a, b): return min(a, b)
_e = 1<<60 # INFの値は適宜
def mapp(f, x): return f+x
def comp(f, g): return f+g
_id = 0
S = LazySegTree(op, _e, mapp, comp, _id, v) # vに初期化の配列
区間加算・区間最大値
from atcoder.lazysegtree import LazySegTree
def op(a, b): return max(a, b)
_e = -(1<<60)
def mapp(f, x): return f+x
def comp(f, g): return f+g
_id = 0
S = LazySegTree(op, _e, mapp, comp, _id, v) # vに初期化の配列
区間加算・区間和
from atcoder.lazysegtree import LazySegTree
def op(a, b):
a_size, a_sum = a
b_size, b_sum = b
return (a_size+b_size, a_sum+b_sum)
_e = (0, 0)
def mapp(f, x):
x_size, x_sum = x
return (x_size, x_sum+f*x_size)
def comp(f, g): return f+g
_id = 0
vv = [(1, vi) for vi in v] # vに初期化の配列
S = LazySegTree(op, _e, mapp, comp, _id, vv)
verify
結果が（区間のサイズ、区間和）の形で返ってくるので、２番目の要素を答えとする。
区間更新・区間最小値
from atcoder.lazysegtree import LazySegTree
def op(a, b): return min(a, b)
_e = 1<<60 # INFの値は適宜
def mapp(f, x): return x if f == _id else f
def comp(f, g): return g if f == _id else f
_id = 1<<61
S = LazySegTree(op, _e, mapp, comp, _id, v) # vに初期化の配列
区間更新・区間最大値
from atcoder.lazysegtree import LazySegTree
def op(a, b): return max(a, b)
_e = -(1<<60) # INFの値は適宜
def mapp(f, x): return x if f == _id else f
def comp(f, g): return g if f == _id else f
_id = 1<<61
S = LazySegTree(op, _e, mapp, comp, _id, v) # vに初期化の配列
区間更新・区間和
from atcoder.lazysegtree import LazySegTree
def op(a, b):
a_size, a_sum = a
b_size, b_sum = b
return (a_size+b_size, a_sum+b_sum)
_e = (0, 0)
def mapp(f, x):
if f == _id: return x
x_size, x_sum = x
return (x_size, f*x_size)
def comp(f, g): return g if f == _id else f
_id = 1<<61
vv = [(1, vi) for vi in v] # vに初期化の配列
S = LazySegTree(op, _e, mapp, comp, _id, vv)
verify
結果が（区間のサイズ、区間和）の形で返ってくるので、２番目の要素を答えとする。
遅延セグ木の主なメソッド
問題を解くときに使うメソッドを挙げます。
説明の中で、セグ木上の$i$番目$(0\le i< N)$の要素を$A_i$と表します。
set(p, x)
$A_p$を$x$に変更します。
get(p)
$A_p$の要素を取得します。
apply(l, r, x)
$A_l ⋯ A_{r-1}$の範囲に$x$を演算します。
区間加算の場合は区間全体に$x$を加算、区間更新の場合は区間を全て$x$で更新します。
prod(l, r)
$op(A_l ⋯ A_{r-1})$の結果を取得します。
区間最小の場合は区間の最小値、区間和の場合は区間の合計を取得します。
おわりに
コンテスト中は時間が無いのでこの記事を見て良いですが、変なものをセグ木に乗せるためには内部の理解が必須です。
コンテスト後にデバッグ出力などをしながらこのコードが何をしているかをぜひ理解してください。
特に、区間更新・区間和などは正しくクエリに答えるため工夫をしています。
また、ここで出てこないセグ木上でできることとして、max_right、min_leftというものもあります。
遅延セグ木やセグ木自体の説明は他の方の記事が詳しいので、自分で調べてみてください。
参考
この記事は以下の記事のPython版として作成しました。
verifyに使ったサイト