遅延セグ木,特に AtCoder Library (ACL) の lazysegtree
の使い方について,解説記事を書きました.
→ 遅延伝播セグメント木の使い方,ACLPC: K – Range Affine Range Sum の解説
この記事では,上の記事ではカバーしきれなかった躓きポイントを,以下の問題を解きながら解消します:
- ACL Beginner Contest: E - Replace Digits
- AtCoder Beginner Contest 177: F - I hate Shortest Path Problem
- AtCoder Library Practice Contest: L - Lazy Segment Tree
このページの解説は,上の記事の内容に基づいているので,まずは先にそちらをご覧になることをお薦めします.$s_{[l, r)}$ など,上の記事で定義した記号も使っています.
ACLBC: E - Replace Digits
問題ページ: ACL Beginner Contest: E - Replace Digits
まず,遅延伝播セグメント木の使い方,ACLPC: K – Range Affine Range Sum の解説 に書いてある「条件 4 〜 5」を確認します.どちらも満たすことが分かります.
次に,情報 $s_{[l, r)}$ を適当に構成してみて,「条件 1 〜 3」が成り立っているかを確認します.例えば $s_{[l, r)} :=$「$a_{[l, r)}$ を十進法の整数と見なし,$998244353$ で割った余り」とすると,条件 1 は満たしますが条件 2 を満たさないことが分かります.これは \[ s_{[l, r)} = \big( s_{[l, m)} \times 10^{\red{r-m}} + s_{[m, r)} \big) \bmod 998244353 \] ですが,$a_{[m, r)}$ の長さの情報 $\red{r-m}$ を捨ててしまったことが原因です.
よって,ACLPC: K 問題と同様に,$s_{[l, r)}$ に区間長 $r-l$ の情報を追加すれば良さそうです.実際これで条件 1 〜 3 をすべて満たすことが確認できます.
条件の確認の際に得られた式を使うと,S, F
と op, e, mapping, composition, id
の定義は以下のようになります:
struct S {
mint val;
int len;
};
using F = int;
S op(S sl, S sr) {
return {sl.val * ten[sr.len] + sr.val, sl.len + sr.len};
}
S e() { return {0, 0}; }
S mapping(F f, S s) {
if (f == -1) return s;
return {f * one[s.len], s.len};
}
F composition(F f, F g) {
if (f == -1) return g;
return f;
}
F id() { return -1; }
コード全体はこちら: AC コード (C++)
実装についての補足
S, F
が $1$ 変数の場合,構造体を使わずusing F = int;
などと書くことができます(6 行目)ten
とone
という配列を使っています(9,16 行目).これはそれぞれ $100\cdots0$ と $111\cdots1$ を $998244353$ で割った余りを前計算したものです.計算量を減らすためにこのようにしています.- 問題で与えられた更新クエリは
1
から9
の整数値で表せますが,このうちどれも「何もしない」更新クエリid
には対応しません.そこで,「ありえない値」-1
がid
に対応する,と勝手に決めました(24 行目).そして,関数mapping, composition
内で,クエリを表す変数f
の値が-1
かどうかで場合分けしています(15,20 行目).遅延セグ木解説記事の「補足」も参照してください.
ABC177: F - I hate Shortest Path Problem
問題ページ: AtCoder Beginner Contest 177: F - I hate Shortest Path Problem
この問題を考察すると,任意の区間 $[l, r)$ に対して,以下の $2$ つのクエリが処理できれば解けることが分かります:
- 区間取得クエリ: $a_{[l, r)}$ の最小値を答える,
- 区間更新クエリ: 整数 $x$ が与えられる.各 $i \in [l, r)$ に対し $a_i \gets x + i$ と更新する.
これは遅延セグ木で実現できます.
いつもどおり,条件を確認しましょう.条件 4 〜 5 を満たすことは分かります.
次に,$s_{[l, r)} := $「$a_{[l, r)}$ の最小値」としてみると,条件 1,2 は満たしますが,条件 3 を満たしません.
実際,区間 $[l, r)$ に更新クエリが来たとき,$s_{[l, r)}$ を \[ s_{[l, r)} \gets \min\{ x+l, x+l+1, \dots, x+r-1 \} = \red{x+l} \] と更新しないといけませんが,区間の左端 $l$ の情報が不足しています.
そこで,$s_{[l, r)}$ に区間の左端の情報を追加すると,無事条件 1 〜 3 を満たすことが確認できます.実装は以下のとおりです:
struct S { int min, l; };
using F = int;
S op(S sl, S sr) { return {min(sl.min, sr.min), min(sl.l, sr.l)}; }
S e() { return {INF, INF}; }
S mapping(F f, S s) {
if (f == INF) return s;
return {s.l + f, s.l};
}
F composition(F f, F g) {
if (f == INF) return g;
return f;
}
F id() { return INF; }
コード全体はこちら: 提出コード (C++)(読みやすさのために ACL を展開していないので CE になっています)
実装についての補足
- 関数
e
には長さ $0$ の区間の情報 $s_{[i, i)}$ を書くという話でしたが,今回はこれが $i$ に依存しています. しかし関数e
に引数を与えることはできません. このような場合は,任意(問題で考えている範囲)のS
型の変数s
に対し「op(s, e())
とop(e(), s)
の返り値がともにs
に等しくなる」ように,適当にe
を定めます. - そのような
e
を見つけるのが難しい場合は,e
をINF
などの「ありえない値」で定義しておいて,関数op
の中でsl, sr
がありえない値に等しいかどうかで場合分けする,という手もあります. id
をありえない値INF
に設定しているのは,上で説明した ACLBC: E 問題と同様です
ACLPC: L - Lazy Segment Tree
問題ページ: AtCoder Library Practice Contest: L - Lazy Segment Tree
何もしない更新クエリも来るものと考えると,更新クエリは整数 0, 1
で表せます.0
が何もしないこと,1
が $a_i$ の $0,1$ を反転することに対応します.
反転クエリを $2$ 回適用することは何もしないことと等価なので,条件 4 〜 5 を満たすことが分かります.
次に $s_{[l, r)}$ の構成ですが,単に $a_{[l, r)}$ の転倒数 $\texttt{inv}$ を保持するだけでは,条件 2 を満たしません.条件 2 を満たすためには,$a_{[l, r)}$ の中の $0$ の数 $\texttt{c0}$ と $1$ の数 $\texttt{c1}$ も持っていればよいと気づきます.
実際,$s_{[l, r)} = (s^{\texttt{inv}}_{[l, r)}, s^{\texttt{c0}}_{[l, r)}, s^{\texttt{c1}}_{[l, r)})$ とすると,\[s^{\texttt{inv}}_{[l, r)} = \red{s^{\texttt{inv}}_{[l, m)} + s^{\texttt{inv}}_{[m, r)} + s^{\texttt{c1}}_{[l, m)} s^{\texttt{c0}}_{[m, r)}} \] と計算できます($s^{\texttt{c0}}_{[l, r)}, s^{\texttt{c1}}_{[l, r)}$ の計算は簡単です).
このとき,ちゃんと条件 3 も満たします.ちょっと難しいですが,$a_{[l, r)}$ の $0, 1$ が反転されたとき,転倒数は \[ s^{\texttt{inv}}_{[l, r)} \gets \red{s^{\texttt{c0}}_{[l, r)} s^{\texttt{c1}}_{[l, r)} - s^{\texttt{inv}}_{[l, r)}} \] と更新できるためです(やはり $s^{\texttt{c0}}_{[l, r)}, s^{\texttt{c1}}_{[l, r)}$ の更新は簡単です).
上の式を使って実装すると,以下のようになります:
struct S { long long inv, c0, c1; };
using F = int;
S op(S sl, S sr) {
return {sl.inv + sr.inv + sl.c1 * sr.c0, sl.c0 + sr.c0, sl.c1 + sr.c1};
}
S e() { return {0, 0, 0}; }
S mapping(F f, S s) {
if (f == 0) return s;
return {s.c0 * s.c1 - s.inv, s.c1, s.c0};
}
F composition(F f, F g) { return f ^ g; }
F id() { return 0; }
コード全体はこちら: AC コード (C++)
おわりに
lazysegtree
を使う際,いくつか躓きやすいポイントがありますが,この $3$ 問で大部分をカバーできたと思います.練習問題を通して遅延セグ木に対する理解が深まったなら幸いです.
composition
が難しい問題(No.879 Range Mod 2 Query - yukicoder など)は取り上げられなかったので,時間のあるときに別記事で書こうと思います.