tioj 1694 Problem D 你的重生之旅

我真的很喜歡ABCLS的題目XD

雖然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

tioj 1624 快樂設置道路

重新見識到我的debug功力之爛＋＋

爛到透光了，一切敗在sort的位置中

其實就三維DP啦，不是很重要的題目

寫這篇是要說，當把東西移掉時，要記得全部都改
（頭腦要清楚才行）

code: http://codepad.org/NACX8veI

PA 2010 R3－Squared Words

不是這麼想說，但這提真的很水

另外一提我怎麼寫都寫不出來，哪天再回來寫。

而這提其實就枚舉割點，然後LCS

不要以為會TLE，用程式sigma一下就會發現其實是會AC

code: http://codepad.org/uBOk4Tf5

PA2010 R0~R2專區

Rectangles: 枚舉  http://codepad.org/aPJ29Ffi

Orienteering: unique把相同的移掉 http://codepad.org/k4w8eOyD

Mushroom: 來回走在兩相鄰點之間 http://codepad.org/wkxCGXbi

Coins: 用map存o-m*r的最左邊，每次都查看 http://codepad.org/HNfcidQc

tioj 1493 三個農夫

按時間戳記做出一個BIT

剩下就只是些很麻煩的判斷

1. 兩個規則

2. 不能刪超過

code: http://codepad.org/6omTGYug

tioj 1637 我愛台灣

維持stack嚴格遞減?!

看想法啦，而且東西都丟在stack裡好像記憶體變很小

預估有6000K，但出來只有28K

code: http://codepad.org/Ey9tiX3a

tioj 1443 遞迴問題

說真的，好久沒寫程式了，一直努力怕被當的說> <

終於暑假了，今天寫了不錯的怪題?!

這題其實就是給 n ，問 lg(n+1) 的整數部分
（這部份我是印出一大堆東西後判斷出來的）

本來一直怕會有誤差（n大約是100000位吧）

所以寫別的作法，如大數之類的，但100%超時＝＝

最後決定亂寫，直接用換底XD ((居然沒有以二為底的log OoO


code: http://codepad.org/cFB4BO4y