[TIOJ] 2027. 腳步鬆散
題目連結: https://tioj.infor.org/problems/2027 不知道多久沒來這裡了XD，來提供一下兩個這題的做法。 一個是gamegame跟我講的做法，我覺得我應該以前都沒想過，所以紀錄一下這個有趣的作法。 這裡我們將一棵二元樹的節點集合用$\mathbb{T}$表示，並且定義幾個函數 $\text{lch}:\mathbb{T}\rightarrow\mathbb{T}, \text{lch}(x)=\text{left child of }x$ $\text{rch}:\mathbb{T}\rightarrow\mathbb{T}, \text{rch}(x)=\text{right child of }x$ $\text{sz}:\mathbb{T}\rightarrow\mathbb{N}\cup\{0\}, \text{sz}(x)=\text{size of }x$ $\text{w}:\mathbb{T}\rightarrow\mathbb{N}\cup\{0\}, \text{w}(x)=\min(\text{sz}(\text{lch}(x)), \text{sz}(\text{rch}(x)))$ 那首先有個引理：對於任意二元樹$T$都有$\displaystyle\sum_{u \in T}\text{w}(u) = \mathcal{O}(\text{sz}(T) \log \text{sz}(T))$，證明的部分就留給讀者好了(X) 白話文講一點就是如果有一個$N$個節點的二元樹，而我們對於他每個節點作的演算法都只跟那個節點小的子樹的大小有關的話，複雜度就會是$\mathcal{O}(N \log N \cdot \text{單一操作的複雜度} )$。 回到這題，可以發現如果一個區間$[L, R]$的最大值是$a_i$若且唯若$L \in [j, i]$（其中$j$是使得$j a_i$發生的最大的$j$）跟$R \in [i, j]$（其中$j$是使得$i a_i$發生的最小的$j$），而若是我們把這種性質拿去建成一棵二元樹（也就是讓可能的編號$L$都在$i$的左子樹，可能的編號$R$都在$i$的右子樹）的話我們就會拿到 笛卡爾樹 。 有了笛卡爾樹後，我們還需要一個支援插入、刪除、統計有多...