基因改造優化粟米

http://acm.pku.edu.cn/JudgeOnline/problem?id=2019

pku 2019 - 粟米田 (con-field)

這題的特別之處，是有很多不同的algo都可以AC，所以想分享一下不同algo的做法和效率

題目大意:
有個N*N的matrix，每格儲住一個integer
現有K個query，每次抽問一個B*B的範圍中的max-min

(B<=N<=250, K<=100000) ------------------------------------------------------------------------

Algorithm 1: 直接搜索

很直接，每次query就掃哂整個B*B的地方
Time complexity: O(K*N^2)
由於只有N*N種問法，而K>N*N，所以記錄己問過的結果可以加快少少 (呢個方法同樣適用於下面的algo, i.e. K=N^2)
記錄結果的Time complexity: O(N^4)
雖然time complexity仍是很高，但據聞pku的數據很虧，所以仍是過到的

------------------------------------------------------------------------

Algorithm 2: 2D segment tree/2D binary search tree

由於segment tree的強項就是能O(lg N)地找到一段數據中的max, min，因此把它拓展到2D，就能找出一個2D陣列中的max, min
Time complexity: O(N^2*lg N*lg N)
快了很多，但缺點是2D線段樹很惡code，又易有bug
還有，線段樹的特點是要query的range係幾多都得，但呢題一早俾左個range你，所以應存在比segment tree更簡單的方法

------------------------------------------------------------------------

Algorithm 3: pre-compute 所有水平B格中的max, min

以test case做例子 (B=3)

5 1 2 6 3                      
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9

假設先pre-compute 一個 max matrix

5 6 6 * *   // 5=max(5,1,2) ; 6=max(1,2,6) ; 6=max(2,6,3)
5 5 7 * *   // 5=max(1,3,5) ; 5=max(3,5,2) ; 7=max(5,2,7)
7 6 6 * *
9 9 8 * *
9 9 9 * *

這樣的話, 每次找一個正方形區域中的max和min時，只需垂直找一次就得了，因為水平的B格己經找了
例如query(1,2) [左上角為1,2的正方形]

5 1 2 6 3                      
1 3 5 2 7
7 2 4 6 1
9 9 8 6 5
0 6 9 3 9

5 6 6 * *
5 5 7 * *
7 6 6 * *
9 9 8 * *
9 9 9 * *

最大值 = max(6,5,6) = 6
找min也同樣道理

每次query的time complexity: O(N)

問題是，要怎樣pre-compute?

方法一: 每一次都向右掃B格
Time complexity (pre-compute): O(N^3)

方法二: 用monotone queue (deque)

在找第一列的3個max時，
分別求了 max(5,1,2), max(1,2,6), max(2,6,3)

5 1 2 6 3
5 1 2 6 3
5 1 2 6 3

不難看出1,2,6都重覆求了
事實上，這正是sliding window問題
當要找的max/min的range是固定且在slide的時侯，
就可以用monotone queue找!
Time complexity (pre-compute): O(N^2)

query也有方法優化的
注意到每次query也是在max matrix中找一段的max

所以可以先把它轉化成1D segment tree
這樣，每次query的time只需O(lg N)
Time complexity: O(N^2*lg N)

真的不能再優化?
再看一次個max matrix

5 6 6 * *
5 5 7 * *
7 6 6 * *
9 9 8 * *
9 9 9 * *

其實每次query就是找垂直相連B個中的max和min
那可以把他們都pre compute!!!

把max matrix pre compute 後的樣子:

7 6 7 * *    //  7=max(5,5,7)   6=max(6,5,6)   7=max(6,7,6)
9 9 8 * *    //  9=max(5,7,9)   9=max(5,6,9)   8=max(7,6,8)
9 9 9 * *    //  9=max(7,9,9)   9=max(6,9,9)   9=max(6,8,9)
* * * * *
* * * * *

同樣地使用monotone queue去做，總時間O(N^2) compute完畢
每次query: O(1)

Time complexity: O(N^2)

事實上，把max matrix和min matrix都pre compute後，每次query只是

scanf("%d%d",&x,&y);
printf("%d\n",max[x][y]-min[x][y]);

連記錄答案都不用...

monotone queue，繼BIT又一屈機之作

有左monotone，打code好輕鬆