雖然code很長，而且我寫了超久（+ debug）
我開了四個重要的陣列，a, b, c, d
a[i]: 第 1 ~ i 塊自己的逆序數對和（nlgn）
b[i][j]: 第 i 個對第 1~j 塊的逆序數對和（n*sqrt(n) -> 要想一下）
c[i][j]: sigma( k = 1 ~ i )第 k 塊對第 k+1~j 塊的逆序數對和（n*sqrt(n)）
d[0][i]: 第 i 個對自己所屬的塊中的右邊的逆序數對（n*sqrt(n)）
d[1][i]: 第 i 個對自己所屬的塊中的左邊的逆序數對（n*sqrt(n)）
For every query:
用 a 和 b 做出完全包住 『所問的範圍』 的方塊的逆序數對數量O(1)
用 c 和 d 扣掉多出來不在『所問的範圍』的那些逆序數對 O(sqrt(n))
再用神祕的方法O(L) sort 兩坨多出來的，並將他們的逆序數對數加回來O(sqrt(n))
最重要的是，每一塊的數量！
由於我寫的code使得時間複雜度為
T( 5Qx + 4n^2/x + nlgx + n + 0.5*(n^2) / (x^2) )（x為每一塊的數量）
有些不重要可以劃掉 -> T( 5Qx + 4n^2/x )要最小，用算幾不等式
可以得到想要最小時， x = sqrt( 4/5 ) * n / sqrt( q )
code: http://codepad.org/Q1v7RMu8
沒有留言:
張貼留言