6 木構造配列、セグメントツリー練習

セグメントツリーの知識については、こちらを参照してください：《面接筆試算法下》——4 セグメントツリー

フェニックツリーの知識については、こちらを参照してください：《面接筆試算法下》——5 フェニックツリー

HZOJ-331：迷子の牛#

Lost_cows

サンプル入力

サンプル出力

考え方
- 【問題 1】得られた答えは唯一か❓√
  - 後ろから前へ、逆に観察する
  - 最後の小動物の値は、前のすべての小動物に対するもので、つまり全ての情報が分かる
  - したがって、もしその値が $x$ であれば、前に $x$ 匹の小動物がそれより小さい場合、その番号は $x+1$ である
  - さらに：倒数第二の小動物 $y$ について、最後の小動物の番号を除いて、順番に $y+1$ 番目の番号を探す、つまり自分の番号
- 【問題 2】残っている番号をどう知るか❓マーク配列
  - マーク配列を使って、各番号 [インデックス] が使用可能かどうかを記録し、使用可能なら 1、使用不可なら 0
    - この時、マーク配列で 1 にマークされているものが、使用可能な番号である
- 大まかなプロセスは以下の図のように、①→④の順で
  - 現在のマーク配列の中で第 $k$ 個目の 1 に対応するインデックスを数える必要がある
  - 例えば、③④のステップでは、現在の牛は前の 1 匹の牛の番号より大きく、現在の牛の番号は現在残っている使用可能な番号の中で第 2 大の番号、つまり 3 であり、再度マークする
- 【問題変換】マーク配列の前方和
  - 第 $k$ 個目の 1 に対応するインデックスは、実際には前方和を使って得られる
  - マーク配列の第 $x$[番号] 位の前方和は、第 $x$ 位前に使用可能な番号の数 [自分を含む] を表し、つまり $k$[入力 + 1]
  - したがって、前方和配列の中で、初めて現れる【$k$】の値を探し、対応する【$x$】のインデックスを得る
    - 初めて現れることに注意：つまりマーク配列の第 $x$ 位は必ず 1 である必要がある [後に続く 0 は前方和を増加させない]
- 【結論】⭐
  - 後ろから前へ観察し、順次各牛の番号を決定する
    - 残りの使用可能な番号の中から第【入力 + 1】位の番号を探す
  - マーク配列の前方和を維持し、その前方和配列は単調である
    - したがって、前方和配列で二分探索を行い、初めて現れる値を探し、対応するインデックスを得る
  - マーク配列の前方和の維持と単点更新が関わるため、フェニックツリーを使用できる
- 【重要なテクニック】マーク配列、マーク配列の前方和を使用
- 【PS】時間計算量：$O (n\ log\ n)$
コード
- フェニックツリー：マーク配列を維持し、前方和を利用
- 探しているのは初めて現れる【入力 + 1】、対応するのは何位か
  - 初めてに注意！複数の対応する【入力 + 1】のインデックスが存在する可能性があるため、0 の存在による
- 見つけたら、必ずマークすること、1->0
- [PS] 入力は第 2 位から始まる

HZOJ-332：チケット購入#

サンプル入力

サンプル出力

77 33 69 51

考え方
- 上の問題 [HZOJ-331] と似ている
  - 入力の第一列の値 👉 ある人の前に何人いるかを示す
- 同様に逆に推測し、フェニックツリーを使用してマーク配列の前方和を維持し、初めて現れる【入力 + 1】の値のインデックスを探し、そのインデックス [実際の位置] と $val$ を対応させる
コード
- 重要：逆に来る👉特別な二分👉マークする [フェニックツリーを維持]👉答えの配列を保存

HZOJ-328：楼蘭のトーテム#

サンプル入力

5
1 5 3 2 4

サンプル出力

3 4

考え方
- 【注意】入力は $1\to n$ の順列である
- 【重要】ある点について、その点が形成する "^" の数は $a \times b$ である
  - ここで、$a$ は前の値がそれより小さい点の数、$b$ は後の値がそれより小さい点の数
- 【問題】どのようにして迅速に解決するか：前にその点より小さい値 $X$ の要素の数 $a$ を求めるには？
  - マーク配列を利用して、現在の位置の前にどの要素が出現したかを記録し、出現したら 1、そうでなければ 0 でマークする
  - 0️⃣→3️⃣の順で進める：値 $X=4$ に到達した時、すでに値 1、2、3、5 がマークされている。この時、前に $X$ より小さい数 $a=3$ であり、換算すると $b=X - 1 - a = 0$、値 4 をマークする
- 【公式化】現在の要素の値を $X$、要素の位置を $i$ とすると
  - ① 前に $X$ より小さい要素の数は $a$
  - ② 後に $X$ より小さい要素の数は $(X - 1) - a$
  - ③ 前に $X$ より大きい要素の数は $(i - 1) - a$
  - ④ 後に $X$ より大きい要素の数は $(n - X) - ((i - 1) - a)$
  - ⭐ 実際には
    - $a$ は $X$ の位置の前のマーク配列の前方和に等しい；残りの 3 つの数は $a$ を使って換算できる
    - ① × ② で "^" の数を得て、③ × ④ で "V" の数を得る
- 【データ構造】マーク配列の単点修正と前方和のクエリには、フェニックツリーを使用できる
- 【PS】考え方は HZOJ-516：牛の碑文に似ている —— 参考解説
  - HZOJ-516 は直接等式を使って数を計算できる
  - しかし、この問題は大小関係を判断する必要があるため、マーク配列に基づくフェニックツリーを使用した
コード
- マーク配列：出現した要素を 1 でマーク
- 換算公式に注目し、図を描いて理解すること
- [PS] 第 64 行の $val [i]$ を $val [i] + 1$ に変更し、さらに第 58 行の前に移動させることでも同様に機能する [理解を深める]

HZOJ-333：区間最大部分和#

サンプル入力

サンプル出力

2
-1

考え方
- 【重要】区間の最大連続部分和を維持する；セグメントツリーを使用
- 【考察】親ノードが所在する区間の最大部分和は、3 つの可能な出所があり、最大を取る必要がある
  - ① 左部分区間 $max$、② 左部分区間 $rmax$+ 右部分区間 $lmax$、③ 右部分区間 $max$
- 【したがって】維持する必要がある値 [各ノード]
  - 最大部分和 $max$、左側の最大部分和 $lmax$、右側の最大部分和 $rmax$、区間の和$sum$
  - なぜ区間の和 $sum$ を維持する必要があるのか❓
    - $lmax$ と $rmax$ の維持を考える
    - 親ノードが所在する区間の $lmax$ は、2 つの可能な出所があり、最大を取る必要がある
      - Ⅰ) 左部分区間 $lmax$、Ⅱ) 左部分区間 $lmax$+ 右部分区間 $lmax$[条件付き]
      - ❗ そして第 Ⅱ) の出所が成立する条件は、左部分区間の $lmax$ が全体の部分区間を横断すること
      - この条件を判断するよりも、区間の和 $sum$[$\le lmax$] を維持する方が良い
- 【注意】最終的に答えを求める時は、左から右へ順に、2 つずつ結合する
  - 例えば：区間 $|①②③④⑤|$ をクエリする時
  - $①②③④⑤$ の順でノードを巡回する
  - 結合の順序は $①+②$、$①②+③$、$①②③+④$、$①②③④+⑤となり、つまり毎回 2 つのノードを 1 つのノードに結合する
  - 最終的に $①②③④⑤$ が 1 つのノードに結合された後、そのノードに対応する $max$ を出力する
  - 詳細はコードを参照
- [PS] セグメントツリーは少し難しい問題である
コード
- ⭐重要な点：番号 $0\to 2$ の操作
  - 0、sum の使用：条件判断を減らす
  - 1、上方更新戦略：3 つのパラメータを渡すため、便利であり、第 88 行の結合戦略のためでもある
  - 2、クエリの結合戦略：毎回 1 つのノードを結合し、結合したノードを他の変数に一時保存し、再び戻す
- [PS]
  - 区間の修正は含まれないため、このセグメントツリーには下に沈むマーク [遅延マーク] 操作はない
  - 問題の意図に従い、$x>y$ の状況を特別に処理する必要がある

ヒント#

フェニックツリーは一般に前方和の問題を解決するために使用される
セグメントツリーはより広く応用され、一般に前方和の問題を含む区間操作の問題を解決するために使用される
問題の性質に応じて、適切なアルゴリズムとデータ構造を探す