PKU3171-Cleaning Shifts

題目：http://poj.org/problem?id=3171
連題名都一模一樣、同樣來自USACO Silverpku2376-cleaning-shifts的帶權版本
給出N條(10000)區間、選擇該區間的成本以及想覆蓋的範圍[M,E] (0...86399)
問覆蓋所求區間的最小成本，無解輸出-1


程式碼：http://codepad.org/yBOsSnYT
很顯然權重都是1可以貪心，帶權就得轉DP了
以下方便起見設定M=1
定義函式f(x)表示想蓋住[1,x]所需花的最小成本
f(0)=0、其他一開始都是無限大
所以很顯然的，對每一條區間假設[p,q]成本r
進行更新f(q) = f(p-1)+r

但是仔細想想會發現，按照這個定義的話、它的更新具有連帶作用
什麼意思呢？請試想現在進行了賦值f(5)=3
那麼f(4)、f(3)、…不就也連帶的都變成了3嗎？
所以說我們精確的對數組A[]進行賦值A[5]=3
發現f(x)的另外一種寫法：f(x) = min(A[x...E])，也就是從x開始、任何能蓋住比x更遠的方案也該被考慮成是可以蓋住x的方案

所以整個算法的架構大致是
1.對n條區間根據p進行排序(線段覆蓋問題)
2.依序更新，A[q] = f(p-1) + r
3.輸出f(E)的值

好，怎麼實現f(x) = min(A[x...E])呢？網路上都說線段樹、我說不必那麼麻煩

樹狀數組可以求區間[1,x]的最小值

那麼簡單的把數組A反轉，不就可以利用樹狀數組解題了嗎？

於是總複雜度O(nlgm)圓滿AC