我的想法是透過分治去解

就是要取 m 項，有三種可能

1. 取的在 1~n 之間
2. 在 1~/n2
3. n/2+1~n

就這樣一直遞迴下去

更詳細一點就是：

先假設左塊的名字叫 L 然後範圍是 1~n/2 右塊是 R 然後 n/2+1~n 

假設已經算好 L 裡面取 0~n/2 個數字的分別答案 R 也是算好了 接下來就是要合併成一塊大塊的 1~n 名字叫 O

合併的話 在 O 裡面取 x 個 就會是：從 L 裡面取 0 R 裡面取 x , 從 L 取 1 R 裡面取 x-1 ... L 取 x R 取 0  個 這些數的總和就會是在 O 裡面取 x 個算出來的答案

這樣做的複雜度是 O(x)

然後接下來因為有 O(logn) 層 總節點數是 O(nlogn) //可以想成線段樹那樣啦

然後每一層要做的就是從下面的合併 合併的話就會是計算該層要拿 0 個 ~ n 個 所以一次合併就會是 O(n*n)

這樣算起來會發現複雜度是 O(n^3 logn) 會 TLE (我自己拿到 80%)

接下來就是要優化一下

可以發現 每一個節點 最多拿的就是他的節點大小 例如這一個節點代表的是從 k~k+100 這一段的答案，那這一個節點大小就會是 101

所以在合併的過程中，我們只需要計算每一個節點拿 0~sz(node) 個就好!

這樣的複雜度就會變成是 O(2^0*n*n + 2^1*(n/2)*(n/2) + 2^2 *(n/4)(n/4)........+2^(logn)*1*1 ) 

這樣整理起來就會變成是 O(n^2 + (n^2)/2 + (n^2)/4....)

提出 n^2 就會變成是也就是 O(logn * (n^2)) 這樣就 AC 了 雖然複雜度分析沒有那麼直觀?

但那個優化的點應該是非常非常直觀的XD