遅延セグ木に慣れる　AtCoder の練習問題 3 問

2020/09/28

遅延セグ木，特に AtCoder Library (ACL) の lazysegtree の使い方について，解説記事を書きました．
→ 遅延伝播セグメント木の使い方，ACLPC: K – Range Affine Range Sum の解説

この記事では，上の記事ではカバーしきれなかった躓きポイントを，以下の問題を解きながら解消します:

このページの解説は，上の記事の内容に基づいているので，まずは先にそちらをご覧になることをお薦めします．$s_{[l, r)}$ など，上の記事で定義した記号も使っています．

  1. ACLBC: E - Replace Digits
      1. 実装についての補足
  2. ABC177: F - I hate Shortest Path Problem
      1. 実装についての補足
  3. ACLPC: L - Lazy Segment Tree
  4. おわりに

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 など）は取り上げられなかったので，時間のあるときに別記事で書こうと思います．

タイトルとURLをコピーしました