94全國賽 6. 下棋問題

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
數據範圍N到5000，但是記憶體卻只給到約略N^2/2。







首先因為我想不到在線(Inline)的作法，故從離線(Offline)開始想起。



當沒有任何阻隔時，任兩個棋子A, B都可以形成一個矩形。



這個矩形出現的時間是max(A, B)，也就是兩個棋子都被下下去始，直到他們中間有其他棋子出現。



也就是如果我們可以枚舉每對棋子，並且快速地算出這個矩形被破壞的時間，這題便可以做了！



而他被破壞的時間就是這個矩形區間中最早放下去的棋子。



所以變成每次查詢一個矩形，問矩形內最早放下的棋子。



這很明顯就是二維的RMQ問題！而二維RMQ可以用Sparse Table作到每次查詢O(lg^2 N)







所以我們就得到一個算法了：



**枚舉每個矩形，查詢那個區間最早被放下的棋子。



**之後我們會得到N(N-1)/2個區間 每個區間代表這個該個矩形的生命週期。



**之後對這些區間進行排序，線性掃過後可以求出每一個時間點場上"存活"的矩形有幾個。



這樣總複雜度會是O(N^2 lg^2 N)，但是記憶體非常不理想地是(N^2 lg^2 N)，



除了執行速度太慢之外，記憶體空間也不足。











以此，需要更優化此算法。



也就是要在O(N^2)以內的複雜度內求出每個矩形的生命週期。



我們想到了分而治之法。(Divide & Conquer)





首先沿中線將棋盤分為左右兩塊，左塊內的矩形及右塊內的矩形可以透過遞歸做出。



現在我們要處理的就是跨越中間線的矩形。







如上圖所示，該矩形會被中線切割為藍色塊跟紅色塊。



該矩形的死期(?)理當為Min(藍色塊內最早被放下的點, 紅色塊內最早被放下的點)



而該怎麼求出每一個點對的每個色塊呢？



我們繼續觀察下去，觀察P對B這個矩形。



我們會發現他在中間線左邊那個紫色塊完全把上圖藍色塊包含了。







也就是其實我們可以用O(點數)求出左邊每個以P為左下角的色塊 內最早被放下的點，



就只要沿著Y軸遞增掃下去即可。





如此每個矩形只會被中線切一次，故總計算量實際上是O(N^2)，也就是矩形數量。







至於記憶體(內存)不夠的問題呢，會發現只要改一下計算順序，記憶體總共只需要N的常數倍，顯然夠用。

















以上。





=====題外話：=====



這題是在94年全國賽的難題之一，



最近幾年全國賽無論是測試數據強度或是題目難度感覺都有點比不上以往...





當年賽後，有選手提出了這題的在線作法



也就是每次加入一個點，算出這個點增加了幾個、破壞了幾個