Posts

UVa 11456. Trainsorting

Description Erin是一個開火車工程師。他喜歡把車廂按照其重量來安排，重的車廂排在前端。 不幸的是，把車廂排序並不是一件容易的事。你只能將一節車廂加在一列火車的前端或後端。 各個車廂來到火車站的順序及其重量是已經知道的。當每節車廂來到的時候，Erin可以把它加到火車的兩端，或者不加進去。最後，火車的總車廂數是越長越好，不過要記得車廂得按照重量大小排列。 給你按照出現順序各車廂的重量，Erin最長可安排車廂的長度是多少？

Template. Persistent Segment Tree

可持久化線段樹適用於查詢不同版本的線段樹，其運作方式非常簡單，就是將要更改的點先複製一遍，未更改的點則不動。而且每新增一個節點，就建立一個新的root，所以我們就可以透過不同的root來讀取不同版本的值。

UVa 1479. Graph and Queries

Description 給定一張無向圖，有三種操作： D x ：刪除第x條邊 Q x y ：查詢x所在集合裡面第y大的數字，若查詢失敗，則此次查詢的結果為0 C x y ：將第x點的值改成y 最後輸出所有查詢的平均值。