[理工] 演算法問題

[QQ153 (小楊)]

想請問一下這一題
https://imgur.com/8ruyb7f
我覺得跟這題很像想嘗試做看看
但目前沒甚麼想法
在請各位大神指點了
https://imgur.com/bINUZSN
https://imgur.com/lDbeYNCd

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.88.219 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1636326874.A.711.html
推 VF84: 用講的太麻煩，我直接PO圖
→ VF84: https://imgur.com/a/MDRsVOp
→ VF84: 因為你的第二張圖連結掛了，所以我沒有完全參考你給的做法
→ VF84: 簡單來說，就是用 merge sort 的技巧去算
推 VF84: 阿對了，我遞迴沒有給終止條件，不過，隨便啦，重點不在哪裡
→ QQ153: 這樣如果條件給ai>aj的話就是把*2給拿掉而已嗎
→ QQ153: 在此重新附上連結
→ QQ153: http://imgur.com/lbeYNCd
推 VF84: ai>aj 的話，把*2拿掉就可以了沒錯
→ QQ153: 感謝 瞭解了
推 alan23273850: 逆序數對的經典解法就是 merge sort 和 binary
→ alan23273850: indexed tree 兩種而已
推 VF84: binary indexed tree...好懷念的名字
→ VF84: 研究所考試應該不至於出現那種東西www
推 mathtsai: 逆序數對 觀念就是用Divide&Conquer
→ mathtsai: 寫起來和merge sort很像 只是改點東西
→ mathtsai: 在merge的時候順便去計算給定的條件即可