TOJ 219 / 円円想要快點去玩！！

想法：

總之就是無修改強制在線逆序數對。
天啊，這題要預處理的東西多到炸。Orz

假設詢問的 l 戳在 第lid塊，r 戳在 第rid塊。

先把[lid, rid]中全部的逆序數對算出來：

考慮把它分塊處理，每一塊先維護自己的逆序對數。(myinv)
然後對每一塊預處理他到他後面每一塊，所產生的逆序對數。(inv_to)
然後把它弄成前綴和，可以O(1)知道某塊到後面某一塊中所有的逆序對數。(inv_to_sum)

然後再把多算的扣掉：

一開始會算出123456全部的逆序對數。
因為只想要4，所以要想辦法快速的把12356扣掉。

一開始預處理每一個數字對她右邊某一塊產生的逆序對數，和對自己那一塊的。(inv_single_to_rgt)
然後把它弄成前綴和，可以O(1)扣掉123。
往左的就反過來做，(inv_single_to_lft)
也可以O(1)扣掉356。

但是3多扣一次，所以要想辦法把它加回去。
在前面把每一塊的逆序對數算出來的時候，有順便把每一塊都sort好。
所以可以多記一個pos，表示這個數在塊中原本的位置，(sorted)
然後O(K)篩出紅色跟藍色部分，再O(K)把3算出來，加回去。

Code：