2019-12-25

可持久化隊列 Persistent Queue 續

接續前一篇《可持久化隊列 Persistent Queue 序》，開始搬運論文的內容，就當作個翻譯吧

預先評估隊列 (Pre-Evaluation)

SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

初階定義

定義：隊列 $Q = \left \langle L, \; R \right \rangle$ 且滿足 $|R| \le |L|$

$$\begin{aligned} \left [ \; \right ]_{q} &= \left \langle \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle L, \; R \right \rangle | &= |L| + |R| \\ \\ \textit{insert} \; (e, \left \langle L, \; R \right \rangle) &= \textit{makeq} \; (L, \; e : R) \\ \\ \textit{remove} \left \langle L, \; R \right \rangle &= \left \langle \text{hd} \; L, \textit{makeq} \; (\text{tl} \; L, \; R) \right \rangle \\ \\ \textit{makeq} \left \langle L, \; R \right \rangle &= \left \langle L, \; R \right \rangle &\{ |R| \le |L|\} \\ &= \left \langle \textit{rot}(L, R, \left [ \; \right ]), \left [ \; \right ] \right \rangle &\{ |R| = |L| + 1\}\\ \\ \textit{rot}(L, R, A) &= \text{hd} \; R : A & \{ |L| = 0 \} \\ &= \text{hd} \; L : \textit{rot}(\text{tl} \; L, \text{tl} \; R, \text{hd} \; R : A) & \{ |L| > 0 \} \end{aligned}$$

看到這一大串的語法樹，就要開始構思曾經在編譯器學到的 LL Parser，操作完之後仍然是一個隊列，為了找到隊列的頭，我們要去完成 LL(1) 的計算，使用向前探查 (lookahead) 問第一個元素為何。

不幸地，上述語法的 $\textit{remove}$ 為 $\mathcal{O}(\log n)$，其他操作為 $\mathcal{O}(1)$。原因很簡單，當我們不斷地 $\textit{insert}$ 進去時，根據語法樹會不斷地構造長度為 $1,\; 2,\; 4, \cdots, 2^n$ 長度的 $\textit{rot}$ 堆疊，這時候若要看第一個元素為何，運算量就等同於遞迴深度。

縱使我們在每個堆疊建構時，預先計算出 front() 的結果，那麼在 pop() 回傳的時候，仍需要付出代價，而我們更不能在建構子中預先計算出 pop() ，這違反遞迴定義，更會落入退化成線性操作，而不是想要的惰性操作。當瞭解上述的問題後，接下來要想辦法把 $\textit{remove}$ 變成 $\mathcal{O}(1)$ 操作。

進階定義

定義：隊列 $Q = \left \langle L, \; R, \; \hat{L} \right \rangle$ 且滿足 $|R| \le |L| \wedge |\hat{L}| = |L| - |R|$

$$\begin{aligned} \left [ \; \right ]_{q} &= \left \langle \left [ \; \right ], \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle L, \; R, \; \hat{L} \right \rangle | &= |L| + |R| \\ \\ \textit{insert} \; (e, \left \langle L, \; R, \; \hat{L} \right \rangle) &= \textit{makeq} \; (L, \; e : R, \hat{L}) \\ \\ \textit{remove} \left \langle L, \; R, \; \hat{L} \right \rangle &= \left \langle \text{hd} \; L, \textit{makeq} \; (\text{tl} \; L, \; R, \hat{L}) \right \rangle \\ \\ \textit{makeq} \left \langle L, \; R, \; \hat{L} \right \rangle &= \left \langle L, \; R, \; \text{tl} \; \hat{L} \right \rangle &\{ |\hat{L}| > 0\} \\ &= \left \langle L', \left [ \; \right ], L' \right \rangle, \; \text{let} \; L' = \textit{rot}(L, R, \left [ \; \right]) &\{ |\hat{L}| = 0\}\\ \\ \textit{rot}(L, R, A) &= \text{hd} \; R : A & \{ |L| = 0 \} \\ &= \text{hd} \; L : \textit{rot}(\text{tl} \; L, \text{tl} \; R, \text{hd} \; R : A) & \{ |L| > 0 \} \end{aligned}$$

透過額外的 $\hat{L}$，避開了 LL Parser 和 lookahead 造成的遞迴定義，如此一來每一個操作複雜度皆為 $\mathcal{O}(1)$。其概念也很簡單，為了維持條件 $|R| \le |L|$，我們將 $\hat{L}$ 定義為其差值，為即將地部分 $R$ 反轉到變成 $L$ 計數做準備。

特別注意到，在 $\text{makeq}$ 的時候，同步移除掉了一部分的 $\hat{L}$，而在長度 $|\hat{L}| = 0$ 觸發反轉。實作上，可以當作一個長度數值去看待，而在可持久化概念上，它們實際上共享同一塊內存，所以也就沒有太大的差別。

概念與前一篇的 Realtime Queue 構造方式類同。只不過，我們預先將答案放置於 $\textit{rot}$ 堆疊定義中的 $A$ 中，而重複使用了 $\hat{L}$ 找到完成時刻。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

Read More +

2019-12-24

工作應用/可持久化

可持久化隊列 Persistent Queue 序

前言

我們完成了持久化堆疊後，必然要去完成隊列 (Queue)。難度遠比想像中的高，很多人的第一個反應是用兩個指標去完成持久化隊列，分別指向最前和最後的兩個元素。不幸地，直覺無法套用在不同的領域上。

下述為一個例子，假定每一個節點都往後指到下一次會被 pop 的節點，則我們無法同時描述 B 和 C。如果每一個節點都往前指到前一個加入的節點，則無法解決隊列的 pop 操作。上述的兩種設計都無法滿足可持久化的定義，則得到用兩個指標是無法完成可持久化隊列。

A = empty().push(1); // [1]
B = A.push(2);       // [1, 2]
C = A.push(3);       // [1, 3]
D = B.pop();         // [2]

攤銷分析的錯誤

定義：可持久化隊列 $Q = \left \langle L, \; R \right \rangle$

在沒有持久化的要求下，我們的確可以用兩個堆疊 $L, \; R$ 去實作隊列 $Q$。當 $|L| = 0$ 時，令 $L' = \text{Rev}(R), \; R' = \left [ \; \right ]$，每一個操作的時間複雜度為 $\text{amortized} \; \mathcal{O}(1)$。

然而，對於可持久化的場合中，這種忽大忽小的成本是不切實際的，因為持久化會複製整體的攤銷成本，而獨立於前一個狀態。達到真正的即時 (realtime)，必須保證每一個操作 $\mathcal{\Theta}(1)$，才能防止攤銷最慘情況不會發生。

即時隊列 (Realtime)

REAL-TIME QUEUE OPERATIONS IN PURE LISP, Robert HOOD and Robert MEVILL, 1981

這快三十年前的論文，給了我們設計函數式的另一種啟發。不透過函數式語言的語法結構，我們可以很直觀地用傳統算法去模擬可持久化隊列。好比 C++ 中的 vector<T> 或者是 Java 中的ArrayList<T>，每當快滿的時候，我們變將元素複製到兩倍大的容器裡。那可持久化就好比背景程式一般，在每一次操作的過程中，就開始準備好抽換的兩倍容器，直到真的要替換的時候，就可以常數搬移。

定義：隊列 $Q = \left \langle O^{\triangleleft}, I^{\triangleright} \right \rangle$ 且滿足 $|O^{\triangleleft}| \ge |I^{\triangleright}|$

$O^{\triangleleft}$ 表示出隊的堆疊
$I^{\triangleright}$ 表示入隊的堆疊

當發生 $|O^{\triangleleft}| = n, \; |I^{\triangleright}| = n+1$ 時，我們標記這個隊列為 轉移中 (transferring)，此時開始可不滿足上述 $|O^{\triangleleft}| \ge |I^{\triangleright}|$ 的規定。接著，我們將預期在下一次 $|O^{\triangleleft}| = 0$ 的 pop 操作前，變換成 $Q = \left \langle (OI)^{\triangleleft}, \left [ \; \right ] \right \rangle$。因此這中間至少有 $n$ 次的 push/pop 操作，讓我們將轉移中隊列變成正規隊列。

需要以下操作：

將 $I^{\triangleright}$ 的所有元素 pop 至 $I_\text{aux} = I^{\triangleleft}$，需 $n+2$ 步。
將 $O^{\triangleleft}$ 的所有元素 pop 至 $O_\text{aux} = O^{\triangleright}$，需 $n+1$ 步。
將 $O_\text{aux}$ 的所有元素 pop 至 $I_\text{aux}$，$O_\text{new}= (OI)^{\triangleleft}$，需 $n+1$ 步。

共計 $3n+4$ 步。平均在 $n$ 次操作內完成。變成 轉移中 狀態的那一瞬間，操作 $7$ 次，隨後的每一個 push/pop 完成 $3$ 次操作。確保了每一步在常數時間內完成。

在轉移過程中，若進行 push 操作，直接在清空完後的 $I^{\triangleright}$ 上操作、或者 $I_\text{extra}^{\triangleright}$ 。若進行 pop 操作時，步驟 3 的最後幾個會成為多餘操作，故需要額外的計數器統計總共完成了幾個 $O_\text{aux}$ 複製，當完成數量等於當前數量 $|O|$ 便停止轉移，並標記為正規隊列 $Q = \left \langle O_\text{new}^{\triangleleft}, I^{\triangleright} \right \rangle$、或者 $Q = \left \langle O_\text{new}^{\triangleleft}, I_\text{extra}^{\triangleright} \right \rangle$

宣告不可變物件的類別時，以 Java 為例相當棘手，展開代碼會造成進入 HotSpot 的機會變低，傳遞這個多的參數進行轉移卻要用在回傳值上額外宣告變數來接取。因此，透過平均 $3$ 次，可能會需要額外宣告 3 次變數，這對 GC 的壓力非同小可。貪心一點，用常數 4 取代，這麼一來可讀性不會下降太多，代碼也能更明確一點，呼叫 2 次的 2 個操作。

實作時，一個可持久化隊列除了一開始的 2 個堆疊，還要維護轉移狀態 5~6 的狀態空間，因此一個隊列需要 7~8 個欄位。

預先評估隊列 (Pre-Evaluation)

SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

這是另一種設計方法，上述方法用了 7~8 欄位來表示一個隊列，作為一個函數式定義太複雜了，這一概念將只使用 3 個，其他的塞在別的定義中，讓其他函數式定義也能夠共享，下一篇文章再來細說。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

效能評比

以 Java 實作，Realtime 與 Pre-Evaluation 效能差不多，但以 OOP 的角度看來 Realtime 很像當初打比賽的精明能幹，Pre-Evaluation 則是代碼量巨大，擴充概念性高。

Read More +

2019-12-23

工作應用/可持久化

可持久化堆疊操作 Persistent Stack Operators

接續前一篇《可持久化堆疊 Persistent Stack》，接下來要探討可持久化堆疊相互操作，如何照常在常數複雜度內完成。這一連貫的定義，將在後續的隊列、雙向隊列中使用。

串接 Append

定義：串接堆疊 $A = \text{Append} \; (T, B)$

$$\begin{aligned} \left [ \; \right ]_{\textit{append}} &= \left \langle \left [ \; \right ], \left [ \; \right ] \right \rangle \\ \\ |\left \langle T, \; B \right \rangle | &= |T| + |B| \\ \\ \textit{push} \; (\textit{e}, \left \langle T, \; B \right \rangle) &= \left \langle e : T, \; B \right \rangle \\ \\ \textit{pop} \; (\left \langle T, \; B \right \rangle) &= \left \langle \text{hd} \; T, \left \langle \text{tl} \; T, \; B \right \rangle \right \rangle & \{ |T| > 0 \} \\ &= \left \langle \text{hd} \; B, \text{tl} \; B \right \rangle & \{ |T| = 0 \} \end{aligned}$$

串接兩個堆疊 $T, \; B$，並且 $T$ 放置於頂首、$B$ 放置於末端，這時候串接也可以被視為一個堆疊結構。由於我們只在意堆疊的接口，完成這三項基礎操作並不是難事。皆可以在 $\mathcal{O}(1)$ 內完成。

對於大小這一個計算，要特別小心一個錯誤，如果直接以回傳值 $|T| + |B|$ 撰寫，將在遞迴使用時，其一方也為串接定義出的堆疊而退化成 $\mathcal{O}(n)$ 的計算。因此在宣告時，紀錄大小是很重要的。

此外，我們也很容易遞迴定義出 Append，如果 $T$ 本身也是 Append 出來的結果，那麼 pop 時會付出遞迴深度的代價，按照使用的演算法，這種情況會使得時間複雜度為 $\mathcal{O}(\log n)$。構造時，如果 $T \in \text{Append}$，拆解成 $\text{Append}(T.l, \; \text{Append}(T.r, \; B))$ 可以避免。

我們透過簡單的工廠模式 (Factory Design Pattern)，防止額外的空間宣告，當 $T$ 或者 $B$ 其一為空時，直接回傳其中一方。接著就能保證 $|T| > 0, \; |B| > 0$，操作就能簡化許多。

提取 Take

定義：提取堆疊 $A = \text{Take} \; (n, X)$

$$\begin{aligned} \left [ \; \right ]_{\textit{take}} &= \left \langle 0, X \right \rangle \\ \\ |\left \langle n, X \right \rangle | &= n \\ \\ \textit{push} \; (\textit{e}, \left \langle n, X \right \rangle) &= \text{Append}(e,\; \left \langle n, X \right \rangle) \\ \\ \textit{pop} \; (\left \langle n, X \right \rangle) &= \left [ \; \right ] & \{ n = 1 \} \\ &= \left \langle \text{hd} \; X, \left \langle n-1, \text{tl} \; X \right \rangle \right \rangle & \{ n > 1 \} \end{aligned}$$

只提取堆頂的前 $n$ 個元素，剩餘的都不需要。無疑地，提取堆疊也是可持久化的，並且在 $\mathcal{O}(1)$ 時間內完成所有堆疊操作。但是在 push 操作時，將使用串接操作。

發生遞迴定義時，意即 $X \in \text{Take}$，則必須提取成 $A = \text{Take}(n, \; X.x)$ 防止退化成 $\mathcal{O}(\log n)$

移除 Drop

定義：移除堆疊 $A = \text{Drop} \; (n, X)$

$$\begin{aligned} \text{Drop} \; (n, X) &= X & \{ n = 0 \} \\ &= \text{Drop} \; (n-1, X) & \{ n > 1\} \end{aligned}$$

相反於提取，忽略堆頂的前 $n$ 個元素，從 $n+1$ 個開始算。

這裡僅提供遞迴定義，由於移除操作並非完全的常數操作，一旦需要拿到堆頂的第一個元素時，勢必要運行 $n$ 次。唯有在運行操作中，若 $n \le c$ 小於某個常數定值時，這時候才能把移除操作視為常數且可持久化的堆疊，否則將視為一般的攤平操作。

爾後，我們將提及一些算法的定義 $c = 3$，使用這一個 Drop 操作。實作時要特別小心，同時 X 也是一個移除堆疊，那麼在建構前，必然要將 X 攤平，意即把 n 弄成 0 的表示法。防止 pop 操作時，意外地發生 stack overflow 的慘劇。

或許有人會問為什麼不一開始就攤平，早就是常數操作？其實，這就要看理論目標的最壞情況最小化，常數要怎麼分配到不同操作中。在可持久化的領域中，每一個常數操作的大小是每個操作的最大值，而非加總起來，完全不同於一般算法設計攤銷分析，因此優化的思維要有所轉變。

反轉 Rev

定義：反轉堆疊 $A = \text{Rev} \; (X)$

$$\begin{aligned} \text{Rev} \; (X) &= \text{Rev}'(X, \left [ \; \right ]) & \\ \\ \text{Rev}'(X, A) &= A & \{ |X| = 0\} \\ &= \text{Rev}' \; (\text{tl} \; X, \text{hd} \; X : A) & \{ |X| > 0\} \end{aligned}$$

將整個堆疊 $X$ 反轉後置放成一個堆疊 $A$。

同樣地，若沒有定義 $|X| \le c$，反轉操作也無法在常數時間內完成。網路上許多實作號稱常數、攤銷持久化，實際上若牽涉到回傳反轉的過程，即使做了快取答案，也可以輕易地將它效能擊破。只需要不斷地呼叫反轉那一瞬間的的操作，或者倒退版本再推進一個版本去觸發攤銷的反轉操作，複雜度就會落入 $\mathcal{O}(n)$。

參考資料

SIMPLE AND EFFICIENT PURELY FUNCTIONAL QUEUES AND DEQUES, Chris Okasaki, 1995

來點題目《記憶中的堆疊》

題目描述

不斷地進行「思想實驗」的妮可，終於讓大腦演進到平行思考。假想在腦海裡，我們把狀態以堆疊 (Stack) 的方式儲存，當走投無路的時候，就會退回到上一個狀態，再把新的分支因素堆疊上去。正在全力計算的妮可無法細說每一個思維狀態，而我們可以操作戳記，反推出當前狀態。

操作有以下三種：

0 v: 退回版本 v
1 x: 在當前堆疊，push x 到堆頂
2: 印出當前堆疊狀態

起始版本編號為 0，第 $i$ 次操作版本編號為 $i$。

範例輸入

範例輸出

Read More +

2019-12-22

工作應用/可持久化

可持久化堆疊 Persistent Stack

起因

在某些情況下，我們想要每次操作都能對應一個新的物件，即使變動當前的數據結構，也不影響前一次的數據結構。「可持久化 Persistent」一詞用來描述在這一段時間內，保存所有操作狀態的方法。若用在資料庫儲存概念中，「持久化 Persistence」則是用來描述將內存數據對照寫入檔案的可行性，兩者的意思不盡相同。

在工作發現許多語言開始支援函數式設計，也就是 $\lambda$ 計算 (lambda function)，以現在手上的 Java 開發，主要發生幾個常見的效能問題：

惰性求值 (Lazy Evaluation)：
每一個惰性求值是需要的時候再計算，然而有些歷史代碼並不是這麼回事，導致一部分函數回傳整個串列，因此消耗了至少為 $\mathcal{O}(n)$ 的時間，而非函數式所需要的 $\mathcal{O}(1)$。如果一個函數只針對前 10 個數值感興趣，大部分的資料都會被捨棄掉，在未來使用這些函數接口時，都還要去檢查每一個相關實作是否為真惰性，而非假性惰性。請參閱 Java Stream 串流實作細節。
不可變物件 (Immutable Object)：
對於某些中間表達式，如檔案系統路徑。若要列出一個資料夾下的所有檔案路徑，在上述的惰性求值中，樸素的實作將會把路徑之間的重複不斷複製。正如同經典的字串問題，每串接一個字串，必然會複製一份，倘若複製的順序相反，時間複雜度將從 $\mathcal{O}(n)$ 變成 $\mathcal{O}(n^2)$。

串流操作 Stream 以 functional-style operation 為主，又細分成好幾種操作。即使運行結果相同，造就的效能與可拓展性也不同，如 reduce 和 collect 的差別，都能將一系列的元素縮合成一個，但是 reduce 採用二合一，容易在合成操作上退化成 $\mathcal{O}(n^2)$，對不可變物件操作，其空間消耗量大，唯一個優勢是平行加速的擴充性。相反地，collect 則是逐一將元素納入一個集合，這樣一個簡單的合併操作，是沒辦法并行處理的，好處則是不會產生太多額外使用空間。

為了達到具拓展性且不失效能的設計，函數式編程那些獨特的數據結構和算法，或許能解決我們的問題。

堆疊定義

堆疊 Stack，主要有兩個操作：

$\textit{push} \; (\textit{value})$：將一個元素 $\textit{value}$ 放置到堆頂
$\textit{pop} \; ()$：將堆頂元素移除

課堂上總是會教資料結構，使用鏈結串列 (Linked List) 或者是陣列 (Array) 來實作，每一個操作皆為 $\mathcal{O}(1)$ 常數。而持久化一個堆疊，我們將要針對改變結構內容的操作進行複製。

可持久化堆疊定義

可持久化堆疊 Stack 定義：

$[\;]_{\textit{stack}} = \left \langle [\;] \right \rangle$
$|\left \langle A \right \rangle| = |\left \langle \text{hd} \; A \right \rangle| + |\left \langle \text{tl} \; A \right \rangle|$
$\textit{push} \; (\textit{e}, A) = \left \langle e : A \right \rangle$
$\textit{pop} \; (A) = \left \langle \text{hd} \; A, \left \langle \text{tl} \; A \right \rangle \right \rangle$

上述的數學式

$\text{hd}$ 為堆疊的首元素。另一個使用術語為 $\textit{car}$。
$\text{tl}$ 為剔除首元素之後的結果。另一個使用術語為 $\textit{cdr}$。從堆疊來看，即為回傳指向前一個節點的位置。
$:$ 為串接操作。

這一簡單結構，又被稱作為 list。只允許對堆頂操作的串列，這麼說很混淆，但在函數式設計中，他們通用的 list 就是這麼構造的，在後續的算法中，我們都用可持久化堆疊來表示 list。

以下述的例子，我們構造 4 個堆疊，每一個堆疊指向堆頂元素。對於加入一個元素到堆疊，我們就額外多一個節點指向先前的堆疊；相同地，移除堆頂元素時，回傳前一個堆疊結果。

A = empty.push(X)    // [X]
B = A.push(Y)        // [X, Y]
C = B.push(Z)        // [X, Y, Z]
D = B.push(W)        // [X, Y, W]

相應的儲存圖

   A         B         C
+--+-+    +--+-+    +--+-+
|  |X<----+  |Y<----+  |Z|
+--+-+    +--+^+    +--+-+
              |
              |        D
              |     +--+-+
              +-----+  |W|
                    +--+-+

此時，$D$ 進行 $\textit{pop}$ 操作，回傳值為 $\left \langle W, B \right \rangle$。

最後，對於每一個操作在 $\mathcal{O}(1)$ 時間內完成，需要額外的 $\mathcal{O}(1)$ 空間。對於沒有垃圾回收 (Garbage Collection) 的語言實作上，需要維護參照數量 reference counter 來回收沒有用到的堆疊節點。

Java 實作代碼

更多細節參閱 morris821028/immortal-jellyfish

package persistent.stack;
import persistent.PStack;
/**
 * @author morrisy
 *
 * @param <T> The type of element
 */
public class PersistStack<T> extends PStack<T> {
    @SuppressWarnings("rawtypes")
    private static final PersistStack<?> EMPTY = new PersistStack();
    @SuppressWarnings("unchecked")
    public static <T> PersistStack<T> create() {
        return (PersistStack<T>) EMPTY;
    }
    private final T value;
    private final PersistStack<T> next;
    private final int size;
    private PersistStack() {
        this(null, null, 0);
    }
    private PersistStack(T value, PersistStack<T> next, int size) {
        this.value = value;
        this.next = next;
        this.size = size;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public int size() {
        return size;
    }
    public PersistStack<T> clear() {
        return create();
    }
    public T top() {
        if (isEmpty())
            return null;
        return value;
    }
    public PersistStack<T> push(T value) {
        return new PersistStack<>(value, this, size + 1);
    }
    public PersistStack<T> pop() {
        return next != null ? next : create();
    }
}

Read More +

2019-08-09

手札日記

我們是否交會於一點

距離上一次撰寫已經過了六個月，原以為有很多故事可以分享，但卻發現工作後的變化並沒有太多。每天就這麼兩點一線地不斷往返，在通勤往返的路上，尋求那麼一點不同。久而久之，擠身在擁擠的人群中只能感受到與自己對話，那種刻骨銘心的衝勁逐漸地消失。

工作

從二月開始到八月，工作仍然繞著程式效能在轉，而我早已忘了給予的目標是什麼，看到路上的石子擋路，就拿著大學的基礎理論一路清下去，問題並不難、演算法也並不深。放在那兒好幾年，對我來說不是滋味。

隨著代碼的增長，一定會有人在之後不斷地照著這個思路複製下去，問題就如雪球般地越來越大。「能混就混吧，這樣才能在社會裡討好關係」－到了工作場所後，不是範圍內的事情，即使點出了錯誤，甚至還順便修了它，也不見得是件好事。這樣做下去，甚至還引起了質疑的氛圍，之後就這麼把工作丟給對方去做，要不然就是不給你權限做任何改變。

逐漸地，無法共同成長的我們，也無法將理想好好地發揮，那到底要怎麼好好地顧及這一切，明明能預先看到的問題，現在卻只能無助地看著危機不斷發生。

「即便如此，他們說的話我全都照做」－《我要準時下班》

起初，總指派著新的功能要著設想架構，但是發現提出來也只有自己去做，大家正襟危坐地聽著規劃，最後問著「大概要花多久的時間，才能看到你們完成？」此時，心中灰了一片。「原來不是要一起走啊」

然而，那些提著都是建立在原有的架構技術下。不斷地嘗試挖掘未來時，卻發現產品的各方面都還欠缺相當嚴重，於是不斷地修正效能、演算法、架構完整與防呆寫法，每天修改上千行的代碼，整體加速了好兩三倍以上，使用內存也少了一大半去，甚至在長期使用的穩定性給予大幅度地調整。

「旁邊的項目有點不妙」－《賢惠幼妻仙狐小姐》

在某些層面上，這的確已經超出了原先設定的目標，但也沒有負責的單位去處理，自己動手下去修純屬逼不得已。面對眾人的期待，我再也沒辦法告訴你們多久能完成那些新功能，但聽到「可是那個不知道還要多久，能不能先 …」、「這問題當初你不是說要解決」諸如此類的話語，心中那股熱火就像少了助燃劑而熄滅。原來我們之間的工作切分得這麼細，真的沒有能力來幫忙嗎？明明我只是做基礎功。

"I can do anything, I can do absolutely anything", The Expert

三月到了，櫃台大姊姊離去。四月到了，同期的同事被女友拖著去讀博班。心裡一沉，現在的我就會這麼一直下去，還是聽著家裡人講的，時間一到乾脆出國繼續讀書去。不知道那些未來還帶有著什麼，而到底是為了什麼賺錢？為什麼要工作？

大神傳了 三和大神 的關鍵字給我，又聽著不斷地說不想學技術的烈士們，原先積極向上的朋友們，似乎都逐漸對工作感到人生黯淡。現實早已經變得殘酷不已，社會卻要向我們勸說咬著忍下去，工作就是不斷分析的我們，哪會這麼輕易地照著劇本走。成熟的我們，為了理想而苟且偷生，這才是常態。

「雖然涉足這份工作不是因為想做，但接手了就不能放手不管。雖然涉足這份工作不是因為喜歡，但接手了就不能無功而返，就算我們有誰死了，也不會有人哭，大家肯定會笑著送別，因為誰也不敢保證一定能活到明天」－《灰色：幻影扳機》

六月的某一天，我發現自己到了極限，對於現況的不滿已經淹沒我的思緒。那一天，我沒有選擇，開了一場 “I Don’t Have a Choice” 為題的會議。說著自己報告的時候，只能說著最重要的那 1% 的修改，剩餘的那 99% 對在場的各位也許不是那麼重要。就算是僅僅的那麼 1%，說了仍不能在各位心中占有一席之地，問題還是一再地發生。

光鮮亮麗的專案報告不是我所能給予的，現在的我很在意每一個技術環節，因為沒有一個可以遵循的準則。我沒辦法決定一個醒目的會議標題，告訴著你們有什麼特別突破，現在的我想要尋找恆久不變的原則。這些說起來很傷人，但也是因為我們並沒有共同走到那一步，無法在同一個平台上討論。

每當聽著報告，原先就聽不懂得我，完全學不到任何知識，當不知道一個項目用在哪裡，怎麼記也記不久，而且從來沒有機會使用的話，那真的非常難以體會其狀態。懵懵懂懂地參與，不知所謂的發問。

如果還有更遠得未來，就想要知道如何走得更遠。如果報告總是特例說明，輪到我啟程的那一天，真的會是一樣的情況嗎？不經地懷疑，那一天我仍要自己從零開始研究。

做事就像捏黏土，往那個目標捏去並不難，也許不是很漂亮，但足以觀賞。如果可以對材質有所研究？或者在捏的過程有所遵循的方法？是不是可以更進一步地完成？

工作帶著一種「勿以惡小而為之，勿以善小而不為」的心境處理代碼。然而，什麼是善？什麼是偽善？非與非惡？上帝向工程師下咒，一旦看到令人傷心的代碼，就會渾身劇痛的詛咒，為了避免自身的痛苦，就向所有代碼伸出了援手。是否伸出援手？如果存在一個純粹的善可以行動，那只剩下代碼自己了不是？

「只要看過聽過，亦或者思考過。無論何時都能清楚想起來，到目前為止，這種能力的效果只不過比他人記性好而已」－《重啟咲良田》

「這是因為你的正義感太強，強烈到就像潔癖症或完美主義的程度。上帝向某位少年下咒，一旦看到傷心的人就會渾身劇痛的詛咒」－《重啟咲良田》

「少年為了避免自身的痛苦，就向所有悲傷的人伸出援手，之後上帝做了一個少年的複製品。沒有意識，只會模仿少年行為的複製品，假少年也向所有悲傷的人伸出援手，上帝賦予了真假少年各自的名字。一個叫做善，另一個較偽善。你覺得誰是善？誰又是偽善呢？」－《重啟咲良田》

壞習慣已經養成，思考是難以停止，探究一切可能的心仍處於背景運行中。常常從身邊的人，老是說著我想得太多，應該要好好地放鬆。但是，那是因為我還沒有證明那些不可能，這不就是在三十歲以前的常態嗎？現在的我還不能放棄吧？

「為什麼考慮那些不會發生的事情」－《切爾諾貝利》

「『為什麼考慮那些不會發生的事情』，太完美了，應該把這句話印在我們的貨幣上」－《切爾諾貝利》

「我想我沒法再努力了」－《我要準時下班》

一般向

「抱歉，我逃避到工作裡去了」－《未來的未來》

「男人工作不順利的話，不就無路可逃了嗎」－《房仲女王》

基本上，玩得遊戲還是那十幾年來如一貫的楓之谷，只不過現在裡頭認識的人不多了。有一天，久違上線的人問道：

「如果她不在了，那你怎麼還活著？」
「有嗎？」我心中想著，原來看起來還活著。

這幾個月來，沒有什麼特別的目標。看著美劇看看英文。每個休閒的假日就這樣過著，等級也就這樣子上去。

本吾聖騎士

直到了最近，網上朋友讓我認識了遊戲中的妹子，深入了解了後，沒想到是做 HR 的，談起話來常常總是四處碰壁，完全落不著頭緒。在某一天的上班時間，

「在忙什麼？」友人 A 傳來的訊息
「正處理那些幾何相交的問題，高中數學裡頭的。」看著手裡已經整合好的代碼說道。
「那我們呢？」友人 A 很快速地傳了過來，腦海裡沒有任何應答的方式。

這句話的涵義相當地多樣，似乎就在玩弄著我，想讓我去思考，我們最終是否會交會？咱這輩子還沒看過有人問過這種問題。

起先，我並不怎麼在意這些，不過就是遊戲內的嘛。隨後在情人節的前一周，在好友頻道爆炸性的誤解來了。

「是做哪一種朋友？」友人 B 如此問道
「靈魂之友」我開玩笑地插嘴回覆。
「靈魂擁抱」友人 A 不知道向誰說道

友人 C 無法看到友人 A 的詢問，於是莫名其妙陷入了難以解釋的關係。接著，被拉去解釋，在跳進黃河也洗不清的情況下，突然友人 A 這麼說道

「在等本吾過情人節」

這下子，我選擇了死亡。

Read More +

2019-02-16

解題區/解題區 - Zerojudge

動態幾何史蒂芙的泡泡 (解法 2)

題目描述

在處理完數以百計的政事後，受盡折磨的史蒂芙，打算回家好好地休息。拖著疲倦的身軀，再也無法再容納任何一點複雜計算。從王宮走回寢居的路上，發現身邊所見的事物都不再圓滑，看起來就像是粗糙的幾何多邊形構成的一切。

打算享受著泡泡浴的史蒂芙，看著眼前的多邊形泡泡，失去原本應有的色澤，那透涼的心境更蒙上了一層灰影

「為什麼是我呢？」感嘆道

伸出手戳著眼前的泡泡，卻飄了過去

「區區的泡泡也跟我作對，嗚嗚」

將一個泡泡視為一個簡單多邊形 $A$，方便起見用一個序列 $a_0, a_1, ..., a_{n-1}$ 表示多邊形 $A$ 的每一個頂點，則會有 $n$ 個線段 $\overline{a_0 a_1}, \overline{a_1 a_2}, \cdots, \overline{a_{n-1} a_0}$。

Sample Input

Sample Output

Solution

參閱動態幾何史蒂芙的泡泡 (解法 1)

相較於先前的解法 $\mathcal{O}(\log n) - \mathcal{O}(\ast \sqrt{n})$，相當不穩定的嵌套 KD-BRH 的解法，實際上如果單純針對這一題，可以拋開 region search 的操作，只有完全的詢問點是否在多邊形內部，則可以做到 $\mathcal{O}(\log^2 n)$。

如同一般的射線法，對詢問點拉出無限延長的線，找到與多邊形的邊相交個數。如果單純把每一條邊拿出來看，最暴力的複雜度為 $\mathcal{O}(n)$，現在要減少查閱的邊數，且透過 rank tree 在 $\mathcal{O}(\log n)$ 累計相交數量。

由於給定的座標不需要動態，則著手離散化 $X = x_0, x_1, \cdots, x_n$，線段樹中的每一個點 $u$ 維護一個 rank tree，把包含者個區段 $[x_l, x_r]$ 的線段通通放入，且保證放入的線段彼此之間不相交 (除了兩端點)。如此一來，當詢問一個點，需要探訪 $\mathcal{O}(\log n)$ 個節點，每個節點 $u$ 需要 $\mathcal{O}(\log n)$ 時間來計算相交數量，最後詢問的複雜度為 $\mathcal{O}(\log^2 n)$。同理，修改點的操作也會在 $\mathcal{O}(\log^2 n)$。

實作時，特別注意到與射線方向相同的線段不予處理，按照下面的寫法則是不處理垂直的線段，一來是射線法也不會去計算，二來是線段樹劃分的時候會造成一些邊界問題，由於我們對於點離散，父節點 $[x_l, x_r]$，左右子樹控制的分別為 $[x_l, x_\text{mid}]$、$[x_\text{mid}, x_r]$，劃分時會共用中間點。

即使有了上述的概念來解題，我們仍需要維護 rope data structrue 來維護節點的相鄰關係，可以自己實作任何的 binary tree 來達到 $\mathcal{O}(\log n)$，這裡採用 splay tree 示範。

接下來介紹內建黑魔法 PBDS (policy-based data structure) 和 rope。很多人都提及到這些非正式的 STL 函式庫，只有在 gcc/g++ 裡面才有附錄，如果是 clang 等其他編譯器可能是沒有辦法的。所以上傳相關代碼要看 OJ 是否採用純正的 gcc/g++。

參考資料：

PBDS 比較常用在 rank tree 和 heap，由於代碼量非常多，用內建防止 code length exceed limitation 的出現，也不妨是個好辦法。用 rank tree 的每一個詢問操作皆在 $\mathcal{O}(\log n)$，而 heap 選擇 thin heap 或 pairing heap，除了 pop 操作外，皆為 $\mathcal{O}(1)$，在對最短路徑問題上別有優勢。

而這一題不太適用 SGI rope，原因在於雖為 $\mathcal{O}(\log n)$ 操作，但它原本就為了仿作 string 而強迫變成可持久化的引數結構，導致每一個操作需要額外的開銷來減少內存使用。由於此題經常在單一元素上操作，SGI rope 對於單一元素效能不彰，以造成嚴重的逾時。

這裡仍提及和示範這些概念的資料結構，哪天正式編入標準函式庫，想必效能問題都已解決。

KD BRH AC(0.2s, 10 MB)
PBDS + SPLAY AC(0.3s, 38 MB)
PBDS + SGI rope AC(0.5s, 41 MB)
本機 MINGW gcc 4.9 c++ 11 編譯完運行最大的測資需要 20 倍慢於其他寫法，但是上傳到 ZJ 的 gcc 7 又追回去了。於是下載 CYGWIN gcc 7 測試結果與 ZJ 運行結果相當，對於需要調適的人，建議在新版上測試。

用 splay tree 模擬 rope 的時候，會遇到循序非遞減的走訪，這時候若不斷地旋轉至根，會在之後的操作造成退化，常數稍微大一點，雖然在迭代過程中造就好的快取效能，很快地在 $\mathcal{O}(1)$ 訪問到相鄰的節點，卻在下一次的插入/刪除操作中變慢。一些變異的版本中，如只在插入/刪除操作中旋轉至根，在查找操作中不旋轉，或者限制旋轉的深度。雖然有一些特別的退化操作，splay 仍舊是某些 OS 場景中使用的資料結構，現實總是很特別的。

In 2000, Danny Sleator and Robert Tarjan won the ACM Kanellakis Theory and Practice Award for their papers on splay trees and amortized analysis. Splay trees are used in Windows NT (in the virtual memory, networking, and file system code), the gcc compiler and GNU C++ library, the sed string editor, Fore Systems network routers, the most popular implementation of Unix malloc, Linux loadable kernel modules, and in much other software.

Berkeley eecs April 23, 2014people.eecs.berkeley.edu/~jrs/61b/lec/36

PBDS + SPLAY

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct Mesh {
static const int MAXN = 1e5 + 5;
    int pt[MAXN][2];
    vector<int> X;
    void read(int n) {
        for (int i = 0; i < n; i++)
            scanf("%d %d", &pt[i][0], &pt[i][1]);
        X.clear(); X.reserve(n);
        for (int i = 0; i < n; i++)
            X.push_back(pt[i][0]);
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
    }
} mesh;
class SplayTree {
public:
    struct Node {
        Node *ch[2], *fa;
        int size; int data;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            size = 1;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
    };
    Node *root, *EMPTY;
    void pushdown(Node *u) {}
    void pushup(Node *u) {
        if (u->ch[0] != EMPTY)	pushdown(u->ch[0]);
        if (u->ch[1] != EMPTY)	pushdown(u->ch[1]);
        u->size = 1 + u->ch[0]->size + u->ch[1]->size;
    }
    void setch(Node *p, Node *u, int i) {
        if (p != EMPTY)	p->ch[i] = u;
        if (u != EMPTY)	u->fa = p;
    }
    SplayTree() {
        EMPTY = new Node();
        EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
        EMPTY->size = 0;
    }
    void init() {
        root = EMPTY;
    }
    Node* newNode() {
        Node *u = new Node();
        u->fa = u->ch[0] = u->ch[1] = EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        pushup(y);
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        pushdown(x);
    }
    void splay(Node *x, Node *below) {
        if (x == EMPTY)	return ;
        Node *y, *z;
        deal(x);
        while (!x->is_root() && x->fa != below) {
            y = x->fa, z = y->fa;
            if (!y->is_root() && y->fa != below) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        pushup(x);
        if (x->fa == EMPTY)	root = x;
    }
    Node* prevNode(Node *u) {
        splay(u, EMPTY);
        return maxNode(u->ch[0]);
    }
    Node* nextNode(Node *u) {
        splay(u, EMPTY);
        return minNode(u->ch[1]);
    }
    Node* minNode(Node *u) {
        Node *p = u->fa;
        for (; pushdown(u), u->ch[0] != EMPTY; u = u->ch[0]);
        splay(u, p);
        return u;
    }
    Node* maxNode(Node *u) {
        Node *p = u->fa;
        for (; pushdown(u), u->ch[1] != EMPTY; u = u->ch[1]);
        splay(u, p);
        return u;
    }
    Node* findPos(int pos) { // [0...]
        for (Node *u = root; u != EMPTY;) {
            pushdown(u);
            int t = u->ch[0]->size;
            if (t == pos) {
                splay(u, EMPTY);
                return u;
            }
            if (t > pos)
                u = u->ch[0];
            else
                u = u->ch[1], pos -= t + 1;
        }
        return EMPTY;
    }
    tuple<int, int, int> insert(int data, int pos) {	// make [pos] = data
        Node *p, *q = findPos(pos);
        Node *x = newNode(); x->data = data;
        if (q == EMPTY) {
            p = maxNode(root), splay(p, EMPTY);
            setch(x, p, 0);
            splay(x, EMPTY);
        } else {
            splay(q, EMPTY), p = q->ch[0];
            setch(x, p, 0), setch(x, q, 1);
            setch(q, EMPTY, 0);
            splay(q, EMPTY);
            p = prevNode(x);
        }
        if (p == EMPTY)	p = maxNode(root);
        if (q == EMPTY)	q = minNode(root);
        return make_tuple(p->data, data, q->data);
    }
    tuple<int, int, int> remove(int pos) {
        Node *x = findPos(pos), *p, *q;
        p = prevNode(x), q = nextNode(x);
        if (p != EMPTY && q != EMPTY) {
            setch(p, q, 1);
            p->fa = EMPTY, splay(q, EMPTY);
        } else if (p != EMPTY) {
            p->fa = EMPTY, root = p;
        } else {
            q->fa = EMPTY, root = q;
        }
        int del = x->data;
        delete x;
        if (p == EMPTY)	p = maxNode(root);
        if (q == EMPTY)	q = minNode(root);
        return make_tuple(p->data, del, q->data);
    }
    int size() {
        return root == EMPTY ? 0 : root->size;
    }
} mlist;
struct Pt {
    double x, y;
    Pt() {}
    Pt(int xy[]):Pt(xy[0], xy[1]) {}
    Pt(double x, double y):x(x), y(y) {}
    bool operator<(const Pt &o) const {
        if (x != o.x)	return x < o.x;
        return y < o.y;
    }
};
struct PtP {
    static double x;
    Pt p, q;
    PtP(Pt a, Pt b) {
        p = a, q = b;
        if (q < p)
            swap(p, q);
    }
    double interpolate(const Pt& p1, const Pt& p2, double& x) const {
        if (p1.x == p2.x) return min(p1.y, p2.y);
        return p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
    bool operator<(const PtP &o) const {
        return interpolate(p, q, x) < interpolate(o.p, o.q, x);
    }
};
double PtP::x = 1;
struct SegSeg {
    struct Node {
        Node *lson, *rson;
        tree<pair<PtP, int>, null_type, less<pair<PtP, int>>, rb_tree_tag, tree_order_statistics_node_update> segs;
        Node() {
            lson = rson = NULL;
        }
    };
    Node *root;
    int xn;
    Node* newNode() {
        return new Node();
    }
    void freeNode(Node *u) {
        free(u);
    }
    void init() {
        root = NULL;
        xn = mesh.X.size();
    }
    void insert(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
        insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
        insert(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
    }
    void remove(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
        remove(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
        insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
    }	
    int inside(double x, double y) {
        PtP::x = x;
        return count(root, 0, xn-1, x, y)&1;
    }
    int count(Node* u, int l, int r, double x, double y) {
        if (u == NULL)
            return 0;
        int ret = 0;
        if ((mesh.X[l] > x) != (mesh.X[r] > x))
            ret += u->segs.order_of_key({PtP(Pt(x, y), Pt(x, y)), -1});
        int m = (l+r)/2;
        if (x <= mesh.X[m])
            ret += count(u->lson, l, m, x, y);
        if (x >= mesh.X[m])
            ret += count(u->rson, m, r, x, y);
        return ret;
    }
    void insert(int l, int r, pair<PtP, int> s) {
        if (s.first.p.x != s.first.q.x)
            insert(root, l, r, s);
    }
    void remove(int l, int r, pair<PtP, int> s) {
        if (s.first.p.x != s.first.q.x)
            remove(root, l, r, s);
    }
    void insert(Node* &u, int l, int r, pair<PtP, int> s) {
        if (u == NULL)
            u = newNode();
        if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
            PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
            u->segs.insert(s);
            return;
        }
        int m = (l+r)/2;
        if (s.first.q.x <= mesh.X[m])			insert(u->lson, l, m, s);
        else if (s.first.p.x >= mesh.X[m])	insert(u->rson, m, r, s);
        else	insert(u->lson, l, m, s), insert(u->rson, m, r, s);
    }
    void remove(Node* u, int l, int r, pair<PtP, int> s) {
        if (u == NULL)
            return;
        if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
            PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
            u->segs.erase(s);
            return;
        }
        int m = (l+r)/2;
        if (s.first.q.x <= mesh.X[m])			remove(u->lson, l, m, s);
        else if (s.first.p.x >= mesh.X[m])	remove(u->rson, m, r, s);
        else	remove(u->lson, l, m, s), remove(u->rson, m, r, s);
    }
} mbrh;
int main() {
    int n, m, cmd, x, pos;
    double px, py;
    scanf("%d %d", &n, &m);
    mesh.read(n);
    mlist.init(), mbrh.init();
    for (int i = 0; i < m; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d %d", &x, &pos);
            mbrh.insert(mlist.insert(x, pos));
        } else if (cmd == 2) {
            scanf("%d", &x);
            mbrh.remove(mlist.remove(x));
        } else {
            scanf("%lf %lf", &px, &py);
            puts(mbrh.inside(px, py) ? "1" : "0");
        }
    }
    return 0;
}

PBDS + ROPE

#include <bits/stdc++.h>
using namespace std;
#include <ext/rope>
using namespace __gnu_cxx;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
struct Mesh {
static const int MAXN = 1e5 + 5;
    int pt[MAXN][2];
    vector<int> X;
    void read(int n) {
        for (int i = 0; i < n; i++)
            scanf("%d %d", &pt[i][0], &pt[i][1]);
        X.clear(); X.reserve(n);
        for (int i = 0; i < n; i++)
            X.push_back(pt[i][0]);
        sort(X.begin(), X.end());
        X.erase(unique(X.begin(), X.end()), X.end());
    }
} mesh;
class Rope {
public:
    rope<int> r;
    void init() {
        r.clear();
    }
    int next(rope<int>::const_iterator it) {
        it++;
        if (it == r.end())
            return *r.begin();
        return *it;
    }
    int prev(rope<int>::const_iterator it) {
        if (it == r.begin())
            return *r.rbegin();
        it--;
        return *it;
    }
    tuple<int, int, int> insert(int data, int pos) {
        r.insert(pos, data);
        auto it = r.begin() + pos;
        int p = prev(it);
        int q = next(it);
        return make_tuple(p, data, q);
    }
    tuple<int, int, int> remove(int pos) {
        auto it = r.begin() + pos;
        int del = *it;
        int p = prev(it);
        int q = next(it);
        r.erase(pos, 1);
        return make_tuple(p, del, q);
    }
} mlist;
struct Pt {
    double x, y;
    Pt() {}
    Pt(int xy[]):Pt(xy[0], xy[1]) {}
    Pt(double x, double y):x(x), y(y) {}
    bool operator<(const Pt &o) const {
        if (x != o.x)	return x < o.x;
        return y < o.y;
    }
};
struct PtP {
    static double x;
    Pt p, q;
    PtP(Pt a, Pt b) {
        p = a, q = b;
        if (q < p)
            swap(p, q);
    }
    double interpolate(const Pt& p1, const Pt& p2, double& x) const {
        if (p1.x == p2.x) return min(p1.y, p2.y);
        return p1.y + (p2.y - p1.y) / (p2.x - p1.x) * (x - p1.x);
    }
    bool operator<(const PtP &o) const {
        return interpolate(p, q, x) < interpolate(o.p, o.q, x);
    }
};
double PtP::x = 1;
struct SegSeg {
    struct Node {
        Node *lson, *rson;
        tree<pair<PtP, int>, null_type, less<pair<PtP, int>>, rb_tree_tag, tree_order_statistics_node_update> segs;
        Node() {
            lson = rson = NULL;
        }
    };
    Node *root;
    int xn;
    Node* newNode() {
        return new Node();
    }
    void init() {
        root = NULL;
        xn = mesh.X.size();
    }
    void insert(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
        insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
        insert(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
    }
    void remove(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[q])), q});
        remove(0, xn-1, {PtP(Pt(mesh.pt[q]), Pt(mesh.pt[r])), r});
        insert(0, xn-1, {PtP(Pt(mesh.pt[p]), Pt(mesh.pt[r])), r});
    }	
    int inside(double x, double y) {
        PtP::x = x;
        return count(root, 0, xn-1, x, y)&1;
    }
    int count(Node* u, int l, int r, double x, double y) {
        if (u == NULL)
            return 0;
        int ret = 0;
        if ((mesh.X[l] > x) != (mesh.X[r] > x))
            ret += u->segs.order_of_key({PtP(Pt(x, y), Pt(x, y)), -1});
        if (l == r)
            return ret;
        int m = (l+r)/2;
        if (x <= mesh.X[m])
            ret += count(u->lson, l, m, x, y);
        if (x >= mesh.X[m])
            ret += count(u->rson, m, r, x, y);
        return ret;
    }
    void insert(int l, int r, pair<PtP, int> s) {
        if (s.first.p.x != s.first.q.x)
            insert(root, l, r, s);
    }
    void remove(int l, int r, pair<PtP, int> s) {
        if (s.first.p.x != s.first.q.x)
            remove(root, l, r, s);
    }
    void insert(Node* &u, int l, int r, pair<PtP, int> s) {
        if (u == NULL)
            u = newNode();
        if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
            PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
            u->segs.insert(s);
            return;
        }
        if (l == r)
            return;
        int m = (l+r)/2;
        if (s.first.q.x <= mesh.X[m])			insert(u->lson, l, m, s);
        else if (s.first.p.x >= mesh.X[m])	insert(u->rson, m, r, s);
        else	insert(u->lson, l, m, s), insert(u->rson, m, r, s);
    }
    void remove(Node* &u, int l, int r, pair<PtP, int> s) {
        if (u == NULL)
            return;
        if (s.first.p.x <= mesh.X[l] && mesh.X[r] <= s.first.q.x) {
            PtP::x = (mesh.X[l] + mesh.X[r])/2.0;
            u->segs.erase(s);
            return;
        }
        if (l == r)
            return;
        int m = (l+r)/2;
        if (s.first.q.x <= mesh.X[m])			remove(u->lson, l, m, s);
        else if (s.first.p.x >= mesh.X[m])	remove(u->rson, m, r, s);
        else	remove(u->lson, l, m, s), remove(u->rson, m, r, s);
    }
} mbrh;
int main() {
    int n, m, cmd, x, pos;
    double px, py;
    scanf("%d %d", &n, &m);
    mesh.read(n);
    mlist.init(), mbrh.init();
    for (int i = 0; i < m; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d %d", &x, &pos);
            mbrh.insert(mlist.insert(x, pos));
        } else if (cmd == 2) {
            scanf("%d", &x);
            mbrh.remove(mlist.remove(x));
        } else {
            scanf("%lf %lf", &px, &py);
            puts(mbrh.inside(px, py) ? "1" : "0");
        }
    }
    return 0;
}

Read More +

2019-01-27

手札日記

敲落的聲響

那一刻

2019 年的開始，研發替代役過去一年三個月，迎來人生巔峰的二十五歲。曾經努力積賺的學習，在這個當下不斷地被提取，已經無法再次追逐那夢想中的人生，那等跨不過的門檻，對於不斷地分析計算的我，早已算不出任何的可能性。

「全新投入工作中，過著非常平凡順遂的生活。監視著表面的自己是否有不斷地往前進，責怪著那個自己，為什麼沒有好好面對眼前的重要事物。」－《秒速 5 厘米》

倘若停止督促自己這般前進的動力，又如何面對過去，原本希望在未來有所成就的自己。也許要有所改變，正也因為過去的累積才造就現在的我，如果可以這麼輕易地改變，那思考方式就像徹底換了個人似的，四分五裂。

「過去，一直抱持著專一的新。對於無法維持這種想法的自己，一直以來都無法釋懷。」－《秒速 5 厘米》

即使有了工作，認識了新的同事，那無非也只是個工作，社交禮儀下的對談。彼此之間都過著各自的生活，每當論及自己的話題時，總是不知道要從哪裡找出，不受蜚言蜚語的內容。因為總是過著這樣的生活，每天走著兩點一線的路線，不曾偏離的軌跡要怎麼聊著好幾個日子。

要在外頭活出有趣的日子，那是如此困難的題目，每踏一步就是數以百萬的分枝，一個人也許走到哪算到哪，但總是無法歸納一個「樂」的結語。編出讓其他人能夠理解的話語，不斷地瞞騙自己，事實上並沒有這樣子的感受吧。我們之間並沒有好聊的，沒有交集的交流，就不要增添麻煩給彼此了。

「總覺得…已經很久沒有跟人說過話了。」－《秒速 5 厘米》

講講你喜歡的事情吧。無法輕易地說出喜歡，但從你們看來，擺明就是喜歡某些事情，才至於身邊都是這種事物的存在。這種老是亂下評論的人。若從口中道出「喜歡」兩個字，是否又可以增加對方強而有力的定論。身邊只有那些選項時，也只能從那些裡選，不斷地選了下去，那還能稱作「喜歡」的事物，而不是受到「束縛」的體現嗎？

「"喜歡" 是一個束縛的詞」－《終將成為你》

前一刻

投入工作的那一年裡，不斷地翻盤革新，交付著重大包袱，那些面臨到不得不再次攤開的問題，早已沒有人可以述說那段歷史，而現在束手無撤的工程師們，無疑地想邁向全新的架構，到底要怎麼寫才可以銜接原本的需求，有多少人願意花時間去理解，而又有多少人願意花時間等你，不斷地估算那種看不到結局的日子有多遠，又細數著下一個里程有多近。那種龐大的壓迫，能不斷地走出下一步的策略在哪？

「我該成為怎樣的人，來度過餘生」－《終將成為你》

把畢生所學的技術填充進去，那樣就可以解決了嗎？發現有所缺陷的解法，想著問題以不同方式分解，再以不同方式擊破。想不出來就去休息吧。解解別的題目，再回來思考，重置於不同狀態的思維出發，就有機會看到問題的另一面。

然而，過著不斷轉換的日子，發現也來到了三千五百題，這令人羞於心的數字，表示了閒與宅的程度。而真正聰明的人，理應用最少的工具解決最多的問題，也就是以最少的題數，達成最好的成就。試圖從那些題目中淬煉新想法，果然還太愚笨了些，僅僅只是知道的比人多，卻沒有好好地比任何人都深入了解。

「但是我沒辦法在其他人面前，不做特別的自己」－《終將成為你》

下一刻

一年的過去，收到一些學長們的問候，馬上就猜到是來拉人換工作的。現在的我，有那種能力獲得青睞嗎？而現在的位子，是否只是被人感受到這傢伙堪用？算了一算，那些提及的工作內容與薪水，到底以什麼樣的比例才算活得心安，能否不為了下一個日子前進而煩惱。原本應屬於我的日子，是哪一種？

「雖然很遺憾，才能這種東西是有個體差別的，若用鳥類來舉例，我的羽翼是靠腳踏驅動的那種」－《３月的獅子》

「如果，不像惡鬼般地逼迫自己，滿身大汗地蹬下去，一瞬間就會墜落地面」－《３月的獅子》

「如果停止蹬踏的話，若是將能量用再其他的事情上面，就算只是百分之幾，雖不至於墜下去，高度也會降低」－《３月的獅子》

親人、同學、同事，每一個像是完成里程碑地一一度過了關卡，看到自己的下一關只剩下工作，也不知道工作的下一步是為了生活，而生活要去煩惱工作。如果只是這樣子不斷地循環，定義的輪廓已有了雛形，明瞭一切的那時也到了盡頭。如此地羨慕有目標走到下一步，而我只是在等待事情的落幕。

現在的處境到底是雞生蛋，還是蛋生雞？

「我們要一直活下去哦」－《盾之勇者成名錄》

「我接受了現實，回歸平靜」－《我想吃掉你的胰臟》

Read More +

2019-01-26

解題區/出題解題

動態幾何史蒂芙的泡泡 (解法 1)

題目描述請至 Zerojudge e021: 史蒂芙的泡泡查閱詳細內容

題目描述

打算享受著泡泡浴的史蒂芙，看著眼前的多邊形泡泡，失去原本應有的色澤，那透涼的心境更蒙上了一層灰影

「為什麼是我呢？」感嘆道

伸出手戳著眼前的泡泡，卻飄了過去

「區區的泡泡也跟我作對，嗚嗚」

解法

從能找到的論文「A Unified Approach to Dynamic Point Location, Ray Shooting, and Shortest Paths in Planar Maps」得知操作更新 $\mathcal{O}(\log^3 n)$，詢問操作 $\mathcal{O}(\log n)$，這一個實作難度估計沒辦法在 10K 限制下完成 (代碼上傳長度上限)。

從動態梯形剖分開始，複雜度就相當高了，而論文後要有類似輕重鏈剖分的概念，將對偶圖產生的節點以輕重邊保存，接著再維護雙線輪廓，讓相連的連續重邊可以保存左右兩側的輪廓，… 資訊量龐大，想到一些可能未提及的邊界案例，實作相當困難。而從其他題目的經驗中，當設計到 $\mathcal{O}(\log^2 n)$ 的操作時，由於操作常數大，運行時間可能無法匹敵 $\mathcal{O}(\sqrt{n})$ 的算法。

那麼有沒有其他的替代方案，只需要跑得比暴力法還要快就行？特別小心，暴力法找一個點是否在多邊形內，需要 $\mathcal{O}(n)$ 的時間，且快取效果非常好，很容易做到 SIMD 的平行技術。

首先，解決維護多邊形點集序列，可以使用任何的平衡樹完成，若採用 splay tree 在均攤 $\text{Amortized} \; \mathcal{O}(\log n)$。使用 treap 也可以完成這類操作，還可以做到額外的持久化功能。接著，修改點的操作，可以轉換成替換一個點的下一個點，因此將點放在 KD tree 上，而維護下一個點相當於把每一個節點擴充成 BRH。

接著，當解決點是否在多邊形內時，可走訪 BRH 找射線穿過的交點個數，此時複雜度至少為 $\mathcal{O}(\sqrt{n} + k)$，其中 $k$ 為交點個數。我們可以額外維護多邊形的順逆時針來優化搜尋空間，最後一個接觸的線段方向，額外提供奇偶數來判斷該點是否在內側，然後把射線縮短到交點到詢問點之間。不斷地縮短搜尋空間下，大部分的情況為 $\mathcal{O}(\sqrt{n})$，拋開了原本存在的 $k$。

由於是封閉的簡單多邊形，所以當邊的疏密程度不一時，KD tree 轉換 BRH 會造成額外的負擔，bounding box 無法有效提供分割空間的功能。那麼在實際搜尋情況，額外走訪的節點與平面分布有關，這部分就不好分析。如果有更好的想法，歡迎分享。

現在實作動態 KD tree 必須有替罪羊樹 Scapegoat tree 的概念，再掛上 BRH 的想法，提供了相對有效率的動態方法來查詢點是否在多邊形內部。若把維護點序列的 splay tree 換成 treap，便可以做到持久化的動態幾何操作，這便是一開始想要的目標。

如果梯形剖分也可以持久化？暫時還不想去思考，那思考的容器要多大呢？

參考解法

#include <bits/stdc++.h> 
using namespace std;
struct Mesh {
static const int MAXN = 1e5 + 5;
    int pt[MAXN][2];
    void read(int n) {
        for (int i = 0; i < n; i++)
            scanf("%d %d", &pt[i][0], &pt[i][1]);
    }
} mesh;
class SplayTree {
public:
    struct Node {
        Node *ch[2], *fa;
        int size; int data;
        Node() {
            ch[0] = ch[1] = fa = NULL;
            size = 1;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
    };
    Node *root, *EMPTY;
    void pushdown(Node *u) {}
    void pushup(Node *u) {
        if (u->ch[0] != EMPTY)	pushdown(u->ch[0]);
        if (u->ch[1] != EMPTY)	pushdown(u->ch[1]);
        u->size = 1 + u->ch[0]->size + u->ch[1]->size;
    }
    void setch(Node *p, Node *u, int i) {
        if (p != EMPTY)	p->ch[i] = u;
        if (u != EMPTY)	u->fa = p;
    }
    SplayTree() {
        EMPTY = new Node();
        EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
        EMPTY->size = 0;
    }
    void init() {
        root = EMPTY;
    }
    Node* newNode() {
        Node *u = new Node();
        u->fa = u->ch[0] = u->ch[1] = EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        pushup(y);
    }
    void deal(Node *x) {
        if (!x->is_root())	deal(x->fa);
        pushdown(x);
    }
    void splay(Node *x, Node *below) {
        if (x == EMPTY)	return ;
        Node *y, *z;
        deal(x);
        while (!x->is_root() && x->fa != below) {
            y = x->fa, z = y->fa;
            if (!y->is_root() && y->fa != below) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        pushup(x);
        if (x->fa == EMPTY)	root = x;
    }
    Node* prevNode(Node *u) {
        splay(u, EMPTY);
        return maxNode(u->ch[0]);
    }
    Node* nextNode(Node *u) {
        splay(u, EMPTY);
        return minNode(u->ch[1]);
    }
    Node* minNode(Node *u) {
        Node *p = u->fa;
        for (; pushdown(u), u->ch[0] != EMPTY; u = u->ch[0]);
        splay(u, p);
        return u;
    }
    Node* maxNode(Node *u) {
        Node *p = u->fa;
        for (; pushdown(u), u->ch[1] != EMPTY; u = u->ch[1]);
        splay(u, p);
        return u;
    }
    Node* findPos(int pos) { // [0...]
        for (Node *u = root; u != EMPTY;) {
            pushdown(u);
            int t = u->ch[0]->size;
            if (t == pos) {
                splay(u, EMPTY);
                return u;
            }
            if (t > pos)
                u = u->ch[0];
            else
                u = u->ch[1], pos -= t + 1;
        }
        return EMPTY;
    }
    tuple<int, int, int> insert(int data, int pos) {	// make [pos] = data
        Node *p, *q = findPos(pos);
        Node *x = newNode(); x->data = data;
        if (q == EMPTY) {
            p = maxNode(root), splay(p, EMPTY);
            setch(x, p, 0);
            splay(x, EMPTY);
        } else {
            splay(q, EMPTY), p = q->ch[0];
            setch(x, p, 0), setch(x, q, 1);
            setch(q, EMPTY, 0);
            splay(q, EMPTY);
            p = prevNode(x);
        }
        if (p == EMPTY)	p = maxNode(root);
        if (q == EMPTY)	q = minNode(root);
        return make_tuple(p->data, data, q->data);
    }
    tuple<int, int, int> remove(int pos) {
        Node *x = findPos(pos), *p, *q;
        p = prevNode(x), q = nextNode(x);
        if (p != EMPTY && q != EMPTY) {
            setch(p, q, 1);
            p->fa = EMPTY, splay(q, EMPTY);
        } else if (p != EMPTY) {
            p->fa = EMPTY, root = p;
        } else {
            q->fa = EMPTY, root = q;
        }
        int del = x->data;
        free(x);
        if (p == EMPTY)	p = maxNode(root);
        if (q == EMPTY)	q = minNode(root);
        return make_tuple(p->data, del, q->data);
    }
    int size() {
        return root == EMPTY ? 0 : root->size;
    }
} mlist;
static inline int log2int(int x) {
    return 31 - __builtin_clz(x);
}
static inline int64_t h(int p, int q) {
    return (int64_t) mesh.pt[p][0]*mesh.pt[q][1] - (int64_t) mesh.pt[p][1]*mesh.pt[q][0];
}
struct KDBRH {
static constexpr double ALPHA = 0.75;
static constexpr double LOG_ALPHA = log2(1.0 / ALPHA);
    struct Pt {
        int d[2];
        Pt() {}
        Pt(int xy[]):Pt(xy[0], xy[1]) {}
        Pt(int x, int y) {d[0] = x, d[1] = y;}
        bool operator==(const Pt &x) const {
            return d[0] == x.d[0] && d[1] == x.d[1];
        }
        static Pt NaN() {return Pt(INT_MIN, INT_MIN);}
        int isNaN() {return d[0] == INT_MIN;}
    };
    struct PtP {
        Pt p, q;
        PtP(Pt p, Pt q): p(p), q(q) {}
    };
    struct cmpAxis {
        int k;
        cmpAxis(int k): k(k) {}
        bool operator() (const PtP &x, const PtP &y) const {
            return x.p.d[k] < y.p.d[k];
        }
    };
    struct BBox {
#define KDMIN(a, b, c) {a[0] = min(b[0], c[0]), a[1] = min(b[1], c[1]);}
#define KDMAX(a, b, c) {a[0] = max(b[0], c[0]), a[1] = max(b[1], c[1]);}
        int l[2], r[2];
        BBox() {}
        BBox(int a[], int b[]) {
            KDMIN(l, a, b); KDMAX(r, a, b);
        }
        void expand(Pt p) {
            KDMIN(l, l, p.d); KDMAX(r, r, p.d);
        }
        void expand(BBox b) {
            KDMIN(l, l, b.l); KDMAX(r, r, b.r);
        }
        inline int raycast(double x, double fx, double y) {
            return l[1] <= y && y <= r[1] && r[0] >= x && l[0] <= fx;
        }
        static BBox init() {
            BBox b; b.l[0] = b.l[1] = INT_MAX, b.r[0] = b.r[1] = INT_MIN;
            return b;
        }
    };
    struct Node {
        Node *lson, *rson;
        Pt pt, qt;
        BBox box;
        int size; int8_t used;
        Node() {}
        void init() {
            lson = rson = NULL;
            size = 1, used = 1;
            pt = qt = Pt::NaN();
        }
        bool hasBox() { return box.l[0] <= box.r[0]; }
        void pushup() {
            size = used;
            if (lson)	size += lson->size;
            if (rson)	size += rson->size;
            pushupBox();
        }
        void pushupBox() {
            BBox t = BBox::init();
            if (!qt.isNaN())
                t.expand(pt), t.expand(qt);
            if (lson && lson->hasBox())
                t.expand(lson->box);
            if (rson && rson->hasBox())
                t.expand(rson->box);
            box = t;
        }
        double interpolate(double y) {
            if (pt.d[1] == qt.d[1])	return pt.d[0];
            return pt.d[0] + (qt.d[0] - pt.d[0]) * (y - pt.d[1]) / (qt.d[1] - pt.d[1]);
        }
    };
    Node *root;
    vector<PtP> A;
    int64_t area;
    Node _mem[262144];
    int gc[262144], gci, memi;
    Node* newNode() {
        Node *u = gci >= 0 ? &_mem[gc[gci--]] : &_mem[memi++];
        u->init();
        return u;
    }
    void freeNode(Node *u) {
        gc[++gci] = u-_mem;
    }
    void init() {
        root = NULL, area = 0;
        gci = -1, memi = 0;
    }
    void insert(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        insert(root, 0, Pt(mesh.pt[q]), Pt(mesh.pt[p]), log2int(size()) / LOG_ALPHA);
        changeNode(root, 0, Pt(mesh.pt[r]), Pt(mesh.pt[q]));
        area += h(p, q) + h(q, r) - h(p, r);
    }
    void remove(tuple<int, int, int> e) {
        int p, q, r; tie(p, q, r) = e;
        remove(root, 0, Pt(mesh.pt[q]), log2int(size()) / LOG_ALPHA);
        changeNode(root, 0, Pt(mesh.pt[r]), Pt(mesh.pt[p]));
        area -= h(p, q) + h(q, r) - h(p, r);
    }
    int RAY_T;
    double RAY_X;
    vector<double> X;
    int inside(double x, double y) {
        if (area == 0)	return 0;
        X.clear(), RAY_X = 1e+12, RAY_T = -1;
        raycast(root, x, y);
        if (RAY_T < 0)
            return X.size()&1;
        int pass = (area > 0) == RAY_T;
        for (auto &x : X)
            pass += x <= RAY_X;
        return pass&1;
    }
    int size() { return root == NULL ? 0 : root->size; }
    inline int isbad(Node *u, Node *v) {
        if (u == root)	return 1;
        int l = v ? v->size : 0;
        l = max(l, u->size-u->used-l);
        return l > u->size * ALPHA;
    }
    Node* build(int k, int l, int r) {
        if (l > r)	return NULL;
        int mid = (l + r)>>1;
        Node *ret = newNode();
        sort(A.begin()+l, A.begin()+r+1, cmpAxis(k));
        while (mid > l && A[mid].p.d[k] == A[mid-1].p.d[k])
            mid--;
        tie(ret->pt, ret->qt) = tie(A[mid].p, A[mid].q);
        ret->lson = build(!k, l, mid-1);
        ret->rson = build(!k, mid+1, r);
        ret->pushup();
        return ret;
    }
    void flatten(Node *u) {
        if (!u)	return ;
        flatten(u->lson);
        flatten(u->rson);
        if (u->used)	A.emplace_back(u->pt, u->qt);
        freeNode(u);
    }
    void changeNode(Node *u, int k, Pt x, Pt qt) {
        if (!u)	return;
        if (x == u->pt) {
            u->qt = qt, u->pushupBox();
            return;
        }
        changeNode(x.d[k] < u->pt.d[k] ? u->lson : u->rson, !k, x, qt);
        u->pushupBox();
    }
    void rebuild(Node* &u, int k) {
        A.clear(), A.reserve(u->size);
        flatten(u);
        u = build(k, 0, A.size()-1);
    }
    bool insert(Node* &u, int k, Pt x, Pt y, int d) {
        if (!u) {
            u = newNode(), u->pt = x, u->qt = y, u->pushup();
            return d <= 0;
        }
        if (x == u->pt) {
            u->used = 1, u->qt = y, u->pushup();
            return d <= 0;
        }
        auto &v = x.d[k] < u->pt.d[k] ? u->lson : u->rson;
        int t = insert(v, !k, x, y, d-1);
        u->pushup();
        if (t && !isbad(u, v))
            return 1;
        if (t)	rebuild(u, k);
        return 0;
    }
    bool remove(Node* &u, int k, Pt x, int d) {
        if (!u)
            return d <= 0;
        if (x == u->pt) {
            if (u->lson || u->rson)
                u->used = 0, u->qt = Pt::NaN(), u->pushup();
            else
                freeNode(u), u = NULL;
            return d <= 0;
        }
        auto &v = x.d[k] < u->pt.d[k] ? u->lson : u->rson;
        int t = remove(v, !k, x, d-1);
        u->pushup();
        if (t && !isbad(u, v))
            return 1;
        if (t)	rebuild(u, k);
        return 0;
    }
    inline int cast(Node *u, double x, double y) {
        if (u->qt.isNaN() || (u->pt.d[1] > y) == (u->qt.d[1] > y))
            return 0;
        double tx = u->interpolate(y);
        if (tx <= x || tx > RAY_X)
            return 0;
        RAY_X = tx, RAY_T = u->pt.d[1] < u->qt.d[1];
        X.emplace_back(tx);
        return 1;
    }
    Node* stk[128];
    void raycast(Node *u, double x, double y) {
#define pushstk(u) {*p++ = u;}
        Node **p = stk;
        pushstk(u);
        while (p > stk) {
            u = *--p;
            if (!u || !u->size || !u->box.raycast(x, RAY_X, y))
                continue;
            cast(u, x, y);
            pushstk(u->rson);
            pushstk(u->lson);
        }
    }
} mbrh;
int main() {
    int n, m, cmd, x, pos;
    double px, py;
    scanf("%d %d", &n, &m);
    mesh.read(n);
    mlist.init(), mbrh.init();
    for (int i = 0; i < m; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d %d", &x, &pos);
            mbrh.insert(mlist.insert(x, pos));
        } else if (cmd == 2) {
            scanf("%d", &x);
            mbrh.remove(mlist.remove(x));
        } else {
            scanf("%lf %lf", &px, &py);
            puts(mbrh.inside(px, py) ? "1" : "0");
        }
    }
    return 0;
}

Read More +

2019-01-26

解題區/出題解題

動態樹樹形避難所

題目描述請至 Zerojudge e003: 樹形避難所 I、e004: 樹形避難所 II 查閱詳細內容

樹形避難所 I

在一個樹形避難所中有 $N$ 個房間，待在充滿監視器房間的你，透過監視器的顯示發現存在一些未知的入侵者出現在某些房間。為了保護同伴，你可以選擇開啟或關閉房間之間的通道，而你也會收到來自於某個房間的同伴求救訊號，此時給予所有可能遇見的入侵者數量，以便同伴做好萬全的作戰準備。然而，操縱通道的控制器已不受限制，你只能眼睜睜地看著同伴與入侵者對抗，現在的你 … 做好準備了嗎？

操作 1 $u$ $v$：將房間 $u$ 與 $v$ 的通道開啟
操作 2 $u$ $v$：將房間 $u$ 與 $v$ 的通道關閉
操作 3 $u$ $w$：更正房間 $u$ 為 $w$ 個入侵者
操作 4 $u$：回答來自 $u$ 的求救信號，告知與其可能面臨到的入侵者個數

樹形避難所 II

由於上一個樹形避難所已經不再安全，全員轉移到下一個避難所，新的地方將不再是先前的平面構造，新的避難所建構在地下水層中，每一個房間可以在水中移動，並且打通到上一層的某一個房間。不幸地，新的入侵者更加地難纏，想保護大家的你，想藉由破壞某一個房間，將其相連的下層房間的入侵者一同殲滅，情局不斷地變化，哪一個才是最好的破壞手段呢 …

操作 1 $u$ $v$：將房間 $u$ 與上層房間 $v$ 的通道開啟
操作 2 $u$：關閉房間 $u$ 與上層的通道
操作 3 $u$ $w$：更正房間 $u$ 為 $w$ 個入侵者
操作 4 $u$：估算摧毀房間 $u$，可以殲滅的入侵者個數

分析

這一題對於樹的操作，牽涉到修改邊，修改點權，詢問整個連通的樹大小、以及子樹大小。可以考慮使用 Link/Cut Tree 完成。也有高手使用了離線算法，對操作分治後計算答案，將一個邊的存在時間記錄在某個時間戳記上，整體落在 $\mathcal{O}(M \log M)$，由上而下合併所有存在的邊來完成單一詢問，需要搭配啟發式合併，來指查找根造成的退化，這一點相當地聰明。若強制在線，仍需要使用動態樹完成之。

對於第一題，只有包含前三個操作，可以當作一個無根樹操作，因此在 LCT 中的 $\text{MakeRoot}$ 打上反轉標記，無視原本的父子關係，額外維護一個虛邊上的子樹大小，如此一來就可以計算整個子樹大小。其餘的點權修改就相較於容易許多。對於第二題，便要求有根樹，因此在轉到根節點時，不能打上反轉標記，此時的左子樹為父節點，扣除掉父節點的大小後，便可以得到子樹大小。

動態樹解法：空間複雜度 $\mathcal{O}(N)$，操作複雜度 $\text{Amortized} \; \mathcal{O}(\log N)$
離線解法：空間複雜度 $\mathcal{O}(M \log M)$，整體時間複雜度 $\mathcal{O}(M \log M)$

延伸問題

如果子樹存在等價關係，意即他們會被一個操作同時受到影響，那麼更新會退化嗎？

如果這個問題能被解決，那麼使用相同的概念，便能解決更多的高壓縮架構問題。工作就能輕鬆一些了。

參考解答

樹形避難所 I

#include <bits/stdc++.h>
using namespace std;
  
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 30005;
    struct Node;
    static Node *EMPTY;
    static Node _mem[MAXN];
    static int bufIdx;
    struct Node {
        Node *ch[2], *fa;
        int rev;
        int vsize, size, val;
        void init() {
            ch[0] = ch[1] = fa = NULL;
            size = 0, vsize = 0, rev = 0;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
        	if (rev) {
        		ch[0]->rev ^= 1;
                ch[1]->rev ^= 1;
        		swap(ch[0], ch[1]);
        		rev = 0;
            }
        }
        void pushup() {
        	if (this == EMPTY)
        		return;
        	size = ch[0]->size + ch[1]->size + val + vsize;
        }
    };
    LCT() {
        EMPTY = &_mem[0];
        EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
        EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        u->init();
        u->fa = u->ch[0] = u->ch[1] = EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup(), x->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())   deal(x->fa);
        x->pushdown();
    }
    void splay(Node *x) {
        Node *y, *z;
        deal(x);
        while (!x->is_root()) {
            y = x->fa, z = y->fa;
            if (!y->is_root()) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushdown();
    }
    Node* access(Node *u) {
        Node *v = EMPTY;
        for (; u != EMPTY; u = u->fa) {
            splay(u);
            u->vsize += u->ch[1] != EMPTY ? u->ch[1]->size : 0;
            u->vsize -= v != EMPTY ? v->size : 0;
            u->ch[1] = v;
            u->pushup();
            v = u;
        }
        return v;
    }
    void mk_root(Node *u) {
        access(u)->rev ^= 1, splay(u);
    }
    void cut(Node *x, Node *y) {
    	mk_root(x);
    	access(y), splay(y);
//    	debug(10);
    	assert(y->ch[0] == x);
        y->ch[0] = x->fa = EMPTY;
        y->pushup();
    }
    void link(Node *x, Node *y) {
    	mk_root(y);
    	access(x), splay(x);
        y->fa = x;
        x->vsize += y->size;
        x->pushup();
    }
    Node* find(Node *x) {
        access(x), splay(x);
        for (; x->ch[0] != EMPTY; x = x->ch[0]);
        return x;
    }
    void set(Node *x, int val) {
    	mk_root(x);
    	x->val = val;
    	x->pushup();
    }
    int get(Node *u) {
    	mk_root(u);
    	return u->size;
    }
    int same(Node *x, Node *y) {
        return find(x) == find(y);
    }
    void debug(int n) {
        return;
        puts("==================");
        for (int i = 1; i <= n; i++) {
            Node *u = &_mem[i];
            printf("[%d] %d, %d %d, %d %d %d\n", i, u->fa-_mem, u->ch[0]-_mem, u->ch[1]-_mem, u->size, u->vsize, u->val);
        }
    }
} lct;
LCT::Node *LCT::EMPTY, LCT::_mem[LCT::MAXN];
int LCT::bufIdx;
LCT::Node *node[LCT::MAXN];
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        lct.init();
        int cmd, u, v, w;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &w);
            node[i] = lct.newNode();
            lct.set(node[i], w);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %d", &u, &v);
                lct.link(node[u], node[v]);
            } else if (cmd == 2) {
                scanf("%d %d", &u, &v);
                lct.cut(node[u], node[v]);
            } else if (cmd == 3) {
                scanf("%d %d", &u, &w);
                lct.set(node[u], w);
            } else if (cmd == 4) {
                scanf("%d", &u);
                int p = lct.get(node[u]);
                printf("%d\n", p);
            } else {
                scanf("%d %d", &u, &v);
                int f = lct.same(node[u], node[v]);
                printf("%d\n", f);
            }
            lct.debug(10);
        }
    }
    return 0;
}

樹形避難所 II

#include <bits/stdc++.h>
using namespace std;
  
class LCT { // Link-Cut Tree
public:
    static const int MAXN = 30005;
    struct Node;
    static Node *EMPTY;
    static Node _mem[MAXN];
    static int bufIdx;
    struct Node {
        Node *ch[2], *fa;
        int vsize, size, val;
        void init() {
            ch[0] = ch[1] = fa = NULL;
            size = 0, vsize = 0;
        }
        bool is_root() {
            return fa->ch[0] != this && fa->ch[1] != this;
        }
        void pushdown() {
        }
        void pushup() {
        	if (this == EMPTY)
        		return;
        	size = ch[0]->size + ch[1]->size + val + vsize;
        }
    };
    LCT() {
        EMPTY = &_mem[0];
        EMPTY->fa = EMPTY->ch[0] = EMPTY->ch[1] = EMPTY;
        EMPTY->size = 0;
        bufIdx = 1; 
    }
    void init() {
        bufIdx = 1;
    }
    Node* newNode() {
        Node *u = &_mem[bufIdx++];
        u->init();
        u->fa = u->ch[0] = u->ch[1] = EMPTY;
        return u;
    }
    void rotate(Node *x) {
        Node *y;
        int d;
        y = x->fa, d = y->ch[1] == x ? 1 : 0;
        x->ch[d^1]->fa = y, y->ch[d] = x->ch[d^1];
        x->ch[d^1] = y;
        if (!y->is_root())
            y->fa->ch[y->fa->ch[1] == y] = x;
        x->fa = y->fa, y->fa = x;
        y->pushup(), x->pushup();
    }
    void deal(Node *x) {
        if (!x->is_root())   deal(x->fa);
        x->pushdown();
    }
    void splay(Node *x) {
        Node *y, *z;
        deal(x);
        while (!x->is_root()) {
            y = x->fa, z = y->fa;
            if (!y->is_root()) {
                if (y->ch[0] == x ^ z->ch[0] == y)
                    rotate(x);
                else
                    rotate(y);
            }
            rotate(x);
        }
        x->pushdown();
    }
    Node* access(Node *u) {
        Node *v = EMPTY;
        for (; u != EMPTY; u = u->fa) {
            splay(u);
            u->vsize += u->ch[1] != EMPTY ? u->ch[1]->size : 0;
            u->vsize -= v != EMPTY ? v->size : 0;
            u->ch[1] = v;
            u->pushup();
            v = u;
        }
        return v;
    }
    void mk_root(Node *u) {
        access(u), splay(u);
    }
    void cut(Node *x) {
    	access(x), splay(x);
    	x->ch[0]->fa = EMPTY;
        x->ch[0] = EMPTY;
        x->pushup();
    }
    void link(Node *x, Node *y) {
    	access(x), splay(x);
    	access(y), splay(y);
        x->fa = y;
        y->vsize += x->size;
        y->pushup();
    }
    Node* find(Node *x) {
        access(x), splay(x);
        for (; x->ch[0] != EMPTY; x = x->ch[0]);
        return x;
    }
    void set(Node *x, int val) {
    	mk_root(x);
    	x->val = val;
    	x->pushup();
    }
    int get(Node *u) {
    	mk_root(u);
    	int ret = u->size;
    	if (u->ch[0] != EMPTY)
    		ret -= u->ch[0]->size;
    	return ret;
    }
    int same(Node *x, Node *y) {
        return find(x) == find(y);
    }
    void debug(int n) {
        return;
        puts("==================");
        for (int i = 1; i <= n; i++) {
            Node *u = &_mem[i];
            printf("[%d] %d, %d %d, %d %d %d\n", i, u->fa-_mem, u->ch[0]-_mem, u->ch[1]-_mem, u->size, u->vsize, u->val);
        }
    }
} lct;
LCT::Node *LCT::EMPTY, LCT::_mem[LCT::MAXN];
int LCT::bufIdx;
    LCT::Node *node[LCT::MAXN];
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        lct.init();
        int cmd, u, v, w;
        for (int i = 1; i <= n; i++) {
            scanf("%d", &w);
            node[i] = lct.newNode();
            lct.set(node[i], w);
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %d", &u, &v);
                lct.link(node[u], node[v]);
            } else if (cmd == 2) {
                scanf("%d", &u);
                lct.cut(node[u]);
            } else if (cmd == 3) {
                scanf("%d %d", &u, &w);
                lct.set(node[u], w);
            } else if (cmd == 4) {
                scanf("%d", &u);
                int p = lct.get(node[u]);
                printf("%d\n", p);
            } else {
                scanf("%d %d", &u, &v);
                int f = lct.same(node[u], node[v]);
                printf("%d\n", f);
            }
            lct.debug(4);
        }
    }
    return 0;
}

Read More +

2018-11-25

手札日記

波士頓出差 Cadence, Boston

旅程前言

在碩二實習的時候，有碰到一次到美國波士頓出差的機會，有礙於那時候還是實習且研究生的身分，並沒有與團隊一起去。要是出國消失一周的話，指導教授大概會震怒吧，說不定就沒機會出現在 Cadence。

在 2016 那時，台灣的團隊才成立約一年，所以旅程的目的在於去學習，基本上就是產品架構的設計細節與概念、產品開發的流程。即使跟著去那兒，英文聽說都很糟糕的我，也只能看著投影片發呆吧。在這兩年中，團隊從四個人到七個人的成長，產品開發的控制越來越多到台灣團隊手上。因此，此行目的便不再是學習，要探討未來的發展和一些議題。

在出發之前，整理近幾個月的開發議題，手上有兩個舊有產品 OrbitIO 和 Allegro，修改了大幅度的效能問題，但舊有設計架構問題導致一些加速算法無法相容，光是想著這些設計問題，就不知道要怎麼與那邊的團隊討論，這些都是改動十幾年前的設計，我想代碼大多都朝著只增不減的方向邁進，這些問題很少人願意去著手，要去改那些需要十足的勇氣。然後，莫名其妙被加入了 Mission BraveHeart (任務代號：勇敢的心)，成功便成英雄。

另一個新產品的開發便是這次出發的壓軸，其內容跟公司的 EDM (Engineering Data Management) 產品有著異曲同工之妙，這困擾了我好幾個月，其概念就是強化版的批改娘，最大的不同在於多人協作的平台，要如何做得簡單好用「Simple is Better Than Complex」。

「我要做些什麼」－《昴宿七星》

新產品的開發耗時將近一年，途中不斷地有新的工作要做，所以在好幾個產品跳來跳去。在 Java, C, Python, Javascript, HTML 跳來跳去，精神都快要達到臨界點。由於需求調整，一路上重新構造了好幾次架構，不斷地懷疑自己到底能不能把這個產品拉出來。由於公司與 DARPA (Defense Advanced Research Projects Agency, 國防高等研究計劃署)
的合作計畫，加速了這一個產品開發，在九月多時輪廓總算釐清了，目標在一個多月內把產品最低需求完成。

很多 EDA Tools 都經歷了好幾年的開發，如 OrbitIO 和 Allegro 更是幾十年的產品，支線需求直接在平台上開發比較沒什麼壓力。這次則要完全跳離所有依賴關係，團隊成員中沒有系統架構的經驗，而我這種半吊子只寫過一點點的網站，一點點的系統，一次就要走這麼遠，壓力不容小覷，這一段日子裡都不怎麼好睡。

「感覺我好像越來越不行了」－《青春豬頭少年不會夢到兔女郎學姊》

隔了一個多月，我們做到了嗎？做到哪裡？

開發過程中一直想找人來幫忙，面了一些高手，但面試的標準無從根據，導致錄取的進展不斷延後，於是先下定決心自己來吧，網頁後台各種從零開始，著手架構好的後台與前端網頁，試圖完成像 Github 與 git 這等偉大的目標。急急忙忙地切分模組出來給小夥伴開發，過程中又不斷地與其他成員說明系統的架構朝什麼發展，甚至一連開了整天的會議說明方向。

出發前一周仍然在調整各個模組的名稱，好讓介紹時快速切入要領。不得不佩服同事們的合作，介紹這方面的能力從以前開始都倚靠著別人，終於準備好上路了。

「這個世界，沒有我的容身之地」－《異世界魔王與召喚少女的奴隸魔術》

啟程須知

給第二次出國的我 (第一次出國在泰國比賽)

礙於研發替代役的角色，出發前到外交部領事事務局申辦護照，不再是以前的三年版本，一次到手十年期限的護照。除了要額外帶著役男身分證外，其餘項目皆與一般申請護照無異，只需要一周的工作天，便可以領取護照。接著拿到新的護照，便向公司的 HR 發出出差申請，附上護照明細與旅途時間，通過後大約在一天左右，就可以從役政署的研發替代役網站列印許可通知書。接著，入境美國申請 ESTA，線上填妥細節繳費，列印好拿著這些就可以入境美國。

若需要國外駕車，可額外申請國際駕照，直接拿汽車駕照去監理站換發就好。不過國外租車的額外駕駛需要額外的保險，加一個額外駕駛就額外多一個費用，原則上對於我這種新手，最後沒有用到。

十一月初的波士頓到了將近攝氏零度的氣候，這一次旅程長達十四天，差不多要帶個六天的衣物，由於這麼冷的天氣基本上也不太需要太多外衣，內衣之類的還是需要帶多一點，直接在旅館內乾洗晾乾就好，大部分時間都有暖氣，所以只需要帶一件足夠厚的外套就行，也因為暖氣會不斷地除溼，保濕乳液之類的必須帶好。這次旅程意外地發現自己並不太怕冷，帶太多衣服穿不到，感覺有點傻了，毛襪不帶也沒關係，穿了反而不帶適應走路的步伐而不舒服。圍巾、手套帶著比較好，一下雪整個寒意就透過去。

波士頓之旅

做了近 20 小時的飛機，終於到了美國波士頓，公司在比較偏遠的郊區 Chelmsford，隔天我們便到波士頓市中心附近的 MIT 和 Harvard 參觀，這時間點在感恩節前兩周，又正值假日，基本上都沒什麼學生。看著別人的生活環境，冷到一個很不舒服的季節。

MIT

在市中心晃了好一陣子，傍晚才前往到哈佛大學，然後開始排隊與那個金鞋合照。

Harvard University

工作的第一天，聽著不太明白的產品與客戶發展介紹，第一次與 email 對面的人碰面聊天，上頭的上頭們全都來了，勉勉強強用殘破的英文亂說一通，還好有同事罩著，後面講的介紹一句也不懂，只能東猜猜西猜猜，猜出個什麼來再應付。下午便在討論「勇敢的心」細節，原則上是一個複雜度很難壓低的幾何計算，咱什麼時候變成幾何計算的顧問了？我其實也不算懂啊。

工作的第二天，兵分兩路被拆開到各自的主攻產品討論議題，陸陸續續邀請不同議題的相關成員會面，個人覺得是相當大的陣仗，區區的 Morris 開的議題邀了好幾個不同團隊的成員。由當地的同事主持會議，大多的時間都在聽他們討論，只花了幾分鐘介紹問題的原因、要解決的問題、可能的解決方向，為何需要這麼做？接著的應答就靠神一般同事翻譯。嗚嗚，我好沒用。晚上的時候，波士頓的第一場雪來了。

First Snow in Chelmsford

工作的第三天，新產品決鬥的開始，Made in Taiwan 的武力展示，相當沒有信心去展示那些成果，大部分的架構還不確定能不能發展到那樣子，語言的特性決定發展能力，簡單、好用是否能兩全其美呢，覺得自己的眼界還不夠寬廣，深怕被那些非常非常資深的工程師擊飛，最後倖存！

工作的第四天，趕上公司的三十周年慶，公司租了一台遊艇在波士頓河岸繞了兩個小時，各個同事都在船上閒聊。結果我們台灣的都在玩船外的 table football 而忘了拍團體照 …

Cadence 30th Celebration

工作的第五天，討論要怎麼解決大數據的情況，數據一大只要會動就好，那麼效能就不再重要，但是舊有的操作又不能太慢，毫無用武之地的我，決定來個幻想之旅。最後一晚的聚餐，照片上的兇手替我點了 50 美元的龍蝦，看不懂菜單總是令人宰割。

$50 Lobster

紐約之旅

在忙完一周的工作後，我們便到了第二周的紐約自由行。老實說，一開始的行程是回台灣休息，但是大部分的人都不在台灣，如果回台灣也處於無同事或目標的狀況，所以就跟著跑去紐約了。如此瘋狂的行程，大概就這一次！

「我真的沒有想做的事啊」－《來自繽紛世界的明日》

Read More +

預先評估隊列 (Pre-Evaluation)

初階定義

進階定義

Java 實作代碼

前言

攤銷分析的錯誤

即時隊列 (Realtime)

預先評估隊列 (Pre-Evaluation)

Java 實作代碼

效能評比

串接 Append

提取 Take

移除 Drop

反轉 Rev

參考資料

來點題目 《記憶中的堆疊》

題目描述

範例輸入

範例輸出

起因

堆疊定義

可持久化堆疊定義

Java 實作代碼

工作

一般向

題目描述

Sample Input

Sample Output

Solution

PBDS + SPLAY

PBDS + ROPE

那一刻

前一刻

下一刻

題目描述

解法

參考解法

樹形避難所 I

樹形避難所 II

分析

延伸問題

參考解答

樹形避難所 I

樹形避難所 II

旅程前言

啟程須知

波士頓之旅

紐約之旅

來點題目《記憶中的堆疊》