6 樹狀數組、線段樹練習

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$ 位置之前的前綴和；后三個數量都可以通過 $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 個結點為 1 個結點
  - 最終 $①②③④⑤$ 合併為 1 個結點後，輸出該結點對應的 $max$
  - 具體見代碼
- [PS] 線段樹有點兒難度的題目
代碼
- ⭐關鍵點：標號 $0\to 2$ 的操作
  - 0、sum 的使用：減少條件判斷
  - 1、向上更新策略：傳入 3 個參數，為了方便，也為了第 88 行的合併策略
  - 2、查詢的合併策略：每次合併 1 個結點，將合併的結點暫存到其它變量上，再轉回來
- [PS]
  - 不涉及區間修改，所以此線段數沒有下沉標記 [懶標記] 操作
  - 根據題意，需特殊處理 $x>y$ 的情況

Tips#

樹狀數組一般用於解決前綴和問題
線段樹應用更廣泛，一般用於解決包含前綴和問題的區間操作問題
根據問題性質，尋找合適的算法與數據結構