[問題] 演算法問題

[cutekid (可愛小孩子)]

N 個整數(不重複)

N1,N2,N3,N4...Nn

針對每個 Ni

求 Ni+1,Ni+2,Ni+3...Nn 當中小於 Ni 的值有幾個

例:

Input : 4,3,1,5,2

Output: 3,2,0,1,0

請問這個有比 O(n^2) 更好的算法嗎

謝謝 :)


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 210.61.233.210
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1406882903.A.8DD.html
→ yr:不是排個序就好了？ O(n log n)
→ yr:理解錯問題，請無視 XD
推 yvb:樓上的理解其實也沒錯, 稍微轉化一下, 即可適用此題 :)
→ cutekid:可以請 yvb 大開示一下嗎 :)
推 flere:用線段樹可以做到O(n log n)..感覺有別的方法OAO
推 dreamoon:http://ppt.cc/DEO1
推 dreamoon:這是相關文章，搜尋 逆序數對+樹狀數組應該可以搜到很多
→ dreamoon:東西
推 lNishan:推月神 <(_ _)>
推 FRAXIS:如果是單純算inversion 用線段樹會比較快嘛？
推 johnathan717:如果mergesort排序可以一邊排，一邊數inversions
推 FRAXIS:我也是這樣覺得 使用線段數有什麼好處嘛？
推 fenzhang:線段樹可以處理動態情況，例如每次修改某個數字
推 FRAXIS:那當問題是靜態的時候 線段樹應該就沒有優勢了吧?
推 DJWS:時間複雜度都一樣  有沒有優勢就看實作功力囉
推 suhorng:可能沒有. 當然比賽時線段樹可能有模板, 可以直接套.
→ suhorng:但他常數也可能比較大啦 只不過是 trade-off
推 trail0721: Ni+1,Ni+2,Ni+3...Nn=>有序遞增, i.e; 3,4,5,6,7,8,9..
→ trail0721: 輸入 8 => 輸出 (8-3) = 5
→ trail0721: 哈~~~~ 輕鬆一下...
推 DJWS: 归并树 / 划分树