UVa 11235 – Frequent values

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2176

這題是有點變化的RMQ，複習一下寒假學的線段樹，也可以用Sparse Table來作。

Codeforces 500 E. New Year Domino

http://codeforces.com/contest/500/problem/E

 

http://www.cnblogs.com/ACMDoli/articles/4268340.html
這題很多人都用線段樹和一個我沒看過的東東，而官方題解我也還沒完全理解…
但我覺得上面這人的想法很好懂，而且Code又簡單 <(_ _)>

 

而一開始我的寫法會產生一個問題，也就是在算 ans 時， 假設有 A、B 兩骨牌，有可能發生 A 的位置比 B 左邊， 但是倒下來的覆蓋範圍比B還右邊的情況，由於我是從右邊依序算每個骨牌要倒到最後的 cost， 然而骨牌 X 要倒到 Y 的 ans 是 cost[X] – cost[Y]，若 Y 是 B 的話，那就會多減掉。 所以應該要改成 ans = cost[X] – cost[set of Y]，而詢問set的部分就用disjoint set處理。