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：

103北市賽 1.水晶球 (Crystal Ball)

想法：

對於所有在時間t-1可以到的格子b, 把第t秒的格子b的上下左右d_t格設為true。
雖然看時間複雜度有點危險(O(4*10^8))，
但其實有一些cut可以加(ex. 表被填滿了就跳出)，
又有5秒可以跑，
應該可以直接AC。

Code：

103北市賽 2.得分高手 (Master)

想法：

DP題。
狀態：以座標(i,j)為終點所能得的最高分。
轉移：dp(i,j) = ar(i,j) + max(0,dp(i-1,j),dp(i,j-1))。

Code：

103北市賽 3.領土 (Territory)

想法：

滿裸的凸包+有向面積題。
小高一沒教計算幾何哭哭喔QAQ。

Code：

103北市賽 4.太空迷走 (Astro)

想法：

DP題。
要記錄的狀態有[剩餘能量f，座標p，當前前進方向w]，
轉移的話有dp ( f, p, w ) = min ( dp ( f, p+w, w ) , dp ( f+1, p+其他方向, w) ) + 1，
然後枚舉到終點前的最後一次轉彎，同時更新最佳解。
有點不太懂它給已知最佳解要幹嘛= =。
有些邊界條件不太確定，
但是沒有judge可以傳，範測也過了，
於是乎我就當它是對的吧>///<。

Code：

103北市賽 5.加密金鑰 (Key)

想法：

觀察發現，若存在長度=m的解，那麼對於x<=m均有解。
由這項單調性，可以二分搜長度，
再枚舉這個長度的子字串是否相同即可。

實作上要使用string hash的技巧，
請諸位自己多背一些質數吧^^。

Code：