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$ の状況を処理する必要がある

ヒント#

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