把輸入讀入以後，每一次可以選最右邊且距離不超過 t 的點當下一個剪輯點。
每次讀入一個數字時，保存下列的變數:
當目前數字跟上次剪輯點距離超過 t 時就可以選上一個數字當作下一個剪輯點，可以做到記憶體 O(1)。
首先大前提，我們得需要知道 $x^2 - 2y^2 = 1$ 的正整數解以及 $\binom{m}{2} = n^2$ 的正整數解恰好是一一對應的。這個性質上面步驟一的最後一條式子並不難得出(簡單證明: x 必為奇數，且 x,y 皆為正整數時對應到的 m,n 也都是正整數，反之也是)。有了這個性質的前提，我們可以改求 $x^2 - 2y^2 = 1$ 的第 k 組解來反推 $\binom{m}{2} = n^2$ 的第 k 組解。
由範測輸出的 $(m_1, n_1) = (2, 1)$ 可以得出 $x^2 - 2y^2 = 1$ 的第一組正整數解為 $(x_1, y_1) = (2 \times 2-1, 2 \times 2) = (3, 2)$。
至於如何快速求出第 n 組解，這邊提供兩個常見的做法
上面兩個做法都可以在 O(log n) 的時間求出第 n 項。
假設已求出 $x_k, y_k$，可以用步驟 1 最下面的式子反求:
$m_k = \frac{x_k+1}{2} = (x_k+1) \times 500000004 (\mod 10^9 + 7)$
$n_k = \frac{y_k}{2} = y_k \times 500000004 (\mod 10^9 + 7)$
(假設寶石的顏色數量是 m)
寶石編號一樣，則這個問題等價於求整棵樹的深度，可以 dfs 或 bfs 在 O(n) 的時間求出。
與子問題1相同，針對每種顏色分開去求對應到顏色的最長路，可以在 O(nm) 的時間求出。
首先，寶石的顏色編號雖然很大，但是可以發現最多不會超過 n 種不同的顏色。所以在一開始可以將所有顏色離散化將顏色的編號 map 到編號 1~n 之間。
再來，可以考慮用下列的 dfs 算法來算出答案:
def dfs (node):
set.insertOne(color[child]) # insert color to multiset
for child in childs[node]:
dfs(child)
answer = max(answer, set.maxElementCount())
set.removeOne(color[child]) # remove one color from multiset
這裡提供三種 set 的實作方法:
這三種作法都可以快速得出答案，做法 3 的實作比較簡單並且沒有 log，所以在這邊提供作法 3 的虛擬碼:
def dfs (node):
set.insertOne(color[child]) # insert color to multiset
answer = max(answer, set.count(color[child]))
for child in childs[node]:
dfs(child)
set.removeOne(color[child]) # remove one color from multiset
整體的複雜度
考慮這一題的一維版本: 給一數列，如何求出最大又不超過 K 的連續和?
這裡提供一個基於前綴和 O(n log n) 的做法:
以上可以得到一個在 O(n log n) 時間求出此問題一維版本的作法。
考慮一個 x 座標範圍固定在 x1, x2 之間的子矩陣，這時候最佳的 y 座標範圍 y1, y2 就可以套用上面一維版本的方法做出。
由於 x 上下界共有 O(m2) 種可能，每次沒舉完上下界需要花 O(n log n) 的時間檢查，時間共為 O(m2n log n)。
再來定義 next(l,r) 為:
接下來可以用遞回求出:
可以在均攤 O(n) 的時間遞迴求出。
以下面為例，假設紅色為要反轉的區間
| 2 | 1 | 3 | 5 | 7 | 8 | 6 | 4 | 9 | 10 |
反轉以後，得到新的框架區間
| 2 | 1 | 3 | 5 | 4 | 6 | 8 | 7 | 9 | 10 |
從上面的新框架區間，反回考慮原本翻轉前的位置:
| 2 | 1 | 3 | 5 | 7 | 8 | 6 | 4 | 9 | 10 |
以上面為例子，框架區間 (3,6) 可以看成 3,6 兩個數字(即框架區間的最大及最小的數字)往右延伸的兩個區間。再更一般一點，可以得出下列的結論:
對於某次翻轉後得到的新的框架區間 S(x,y)，必定滿足:
這裡令兩個變數 R 與 S。R 代表某次翻轉的區間，S 代表翻轉過後所生成的某個框架區間(在翻轉後數列的位置)。可以發現 S 與 R 的關係只有下面幾種可能
其他的情形都可以發現 S 即使不需要翻轉也是一個框架區間，並不是新增的矛盾，可以不用考慮。由 S 翻轉後的位置去考慮翻轉前的狀況
(紅=區間R，藍=區間S, M=最大or最小數字的位置)
Case 1:
翻轉後:
| M | M |
翻轉前:
| M | M |
Case 2:
翻轉後:
| M | M |
翻轉前:
| M | M |
上面兩個 case 只考慮 R 在 S 右邊的情況，若反過來考慮，則可以得到與上面觀察相當的結論。
由上面的結論，可以發現只要枚舉下面三個變數
枚舉完方向以後，可以以兩數字為起點 greedy 向左或向右延伸到第一個不在 [i,j] 區間的數字為止。每次枚舉完可以在 O(n) 的時間檢查，時間複雜度為 O(n3)
(做法應該很多種，這裡僅提供一位驗題者的作法做為參考)
可以多 DP 數個表格:
延伸原本 O(n3) 的算法，當枚舉完 i,j 考慮往右或往左延伸到哪時，可以把 mnp[i][j] 或 mxp[i][j] 表格的值拿出來輔助，做出 O(1) 的判斷。
若定義 dp[i] = 最右邊選採礦點 i 且最大的價值總和，可以得到轉移式
\[dp[i] = \max_{j<i 且i,j中間有更高的礦井} dp[j] + v[i]\]對於每個 i，可以由大到小枚舉 j，並維護 i 到 j 之間最高的山 k。這樣狀態一共有 O(n) 個，轉移 O(n)，複雜度 O(n2)。
與上面一樣從左到右算出 dp[i]，多維護幾個 DP 和幾棵樹來加速轉移:
算法如下:
for i in range(1,n+1):
dp[i] = dp2.queryRangeMax(h[i]+1, MAX) + value[i] # h=高度, value=價值, queryRangeMax(l,r) = index [l,r] 區間的 max value
dp1.update(h[i], dp[i]) # update(index, value)
dp2.update(h[i], dp1.queryRangeMax(MIN, h[i]-1))
每次求 DP 值和更新都花 O(log n)，複雜度 O(n log n)。
考慮高度數列「從某個數字往左看的遞增序列」，例如數列 9,7,8,2,4,3,6,5 ，從 3 開始往左會遇到的遞增數列為右邊紅色的部分 9,7,8,2,4,3,6,5。
注意到下面兩件事情:
可以開一個 stack 維護這個往左遞增的數列，並另外開一個變數維護 stack pop 出來座標的最大 dp 值。可以每次轉移均攤 O(1)。
上面的做法還是可以做，但要小心很多邊界情況，例如:
這題的可以觀察的結論非常多，這邊選一些重要的結論列出來。
為了方便討論，y=2 的點簡稱為「上」，y=0 的點簡稱為「中」，y=-2 的點簡稱為「下」。若一個三角形由兩個 y=2 及一個 y=-2 的三角形組成，簡稱為「上上下」。
到這裡為止，我們可以把所有三角形的面積寫成 x 座標的絕對值相加，並且可以得到一些簡單的結論:
枚舉以下數字
算法:
上面的算法，若分別維護上、中、下三個 x 座標的前綴和，可以在 O(1) 得到三角形的面積。由於 d 的值可以用 n 減另外三個變數算出，枚舉量為 O(n3)。
上述做法當枚舉為 a,b 以後，觀察 type C(上中下，且上下 x<0) 與 type D(上中下，且上下 x>0) 的三角形。
可以發現，C三角形和D三角形選的點絕對會互斥。可以看成是在所有 C 和 D 三角形的連集裡選最大的 n-a-b 個。並且一定會滿足性值:
枚舉 a,b 以後，可以用上面兩個條件來二分搜 c,d 的值，可以做到 O(n^2 log n)。
考慮上面兩個做法，在 a 固定，b 遞增 1 的情況，這時候 c,d 只會有幾種變化:
可以在 O(n2) 的時間維護。