# 逆向求解

:::info
有些問題從起點出發難以前進，從終點逆算過程卻意外的容易。
:::

記得有時倒著做比正著做更容易。

:::success
### AtCoder abc216_c - Many Balls
https://atcoder.jp/contests/abc216/tasks/abc216_c
:::

如果從 $0$ 出發，很難確定下一步應該 $+1$ 還是該 $\times2$，畢竟 $\times2$ 成長雖快，但歪掉時很難修正回來，例如剛好乘進 $\frac{N}{2}$ 再多一些些的地方時。

但反過來從終點就很簡單了：

- 如果它是奇數，那 $\times2$ 不可能達成，必然得選 $+1$；
- 如果它是偶數，那 $\times2$ 必然能較快回到 $0$，故必選 $\times2$。

每次的抉擇可以直接由奇偶來決定，只要 $O(1)$ 的計算量；最多 $2$ 次抉擇就會將 $N$ 砍半，因此過程最多 $2\times\log_2 N$ 次，複雜度為 $O(\log N)$。

:::success
### CSES 1163 - Traffic Lights
https://cses.fi/problemset/task/1163/
:::

直接暴力處理的話，每次加入一個點後，重新計算每一段的長度，需要 $O(N)$ 的計算量來維護，整體 $O(N^2)$。

插入一個新的點會導致大量的資料搬動，且必須維持遞增使得容易找出最接近的兩個位置，以找到該切點所影響的線段；

每次切分會導致原有的線段會變短，要維護當前的最長線段，必須能支援刪除最大值後仍能找到下一個最大值。

以上這些都是必要，但目前所學的資料結構難以應對的部份。具體來說必須做到以下：

* 給一整數 $k$ 在一個遞增序列 $A$ 找到位置 $i$ 使得 $A_i<k<A_{i+1}$
* 插入一個整數 $k$ 到一個遞增序列 $A$ 並維持遞增
* 對序列 $A$ 增加或刪除元素後，維護其仍能快速找出最大值

以上任一動作都必須執行 $O(N)$ 的次數，因此每個動作都必須在 $O(\log N)$ 等級的計算量完成，否則都有 TLE 的可能。

:::warning
當然，仰賴目前進度未學過的強大資料結構的話，並不是做不到。只是現在做不到。
:::

考慮一開始先把所有切點放進去，再從最後一個切點開始還原，就變成是把一個一個線段接回去。


維護每個切點的左右鄰居，則和鄰居的距離即為線段的長度，如上圖；刪除切點 $i$ 時左鄰居 $l$ 右側從 $i$ 變成 $r$、右鄰居 $r$ 的左側從 $i$ 變成 $l$，用 linked-list 的概念可以處理。

還原時會產生新線段，長度 $r-l$，直接和當前最長線段比較，即可維護。刪除舊的點維護最長很困難，但加入新的點維護最長很容易。

排序後即可知道所有切點在最後和誰相鄰。

得到做法如下：

1. 對切點序列 $A$ 加入道路最左端和最右端
2. 複製 $A$ 並按位置 sort 變成序列 $B$
3. 對序列 $B$ 每個切點記錄現在的左鄰居切點和右鄰居切點是誰
4. 逆序窮舉 $A$ 對每個切點找到 $B$ 中的位置，將它刪除（讓左鄰居和右鄰居變成相鄰）並更新當前最長

預處理 sort 需要 $O(N\log N)$，計算過程窮舉 $N$ 個點，每個點透過二分搜尋 $O(\log N)$ 找到在 $B$ 中的位置，修改左右鄰居 $O(1)$，總複雜度 $O(N\log N)$。

## 歡樂練習時間

:::success
### ZJ f607 - 切割費用
https://zerojudge.tw/ShowProblem?problemid=f607

APCS 2021/01 p3

:::

{%hackmd @sa072686/__style %}

###### tags: `競程：二章後半`, `競程`