某島

… : "…アッカリ~ン . .. . " .. .
January 30, 2012

SPOJ 2798. Query on a tree again!

Brief description:

… 黑白樹系列問題。。

  • 0 u: 修改,將 u 點反色。
  • 1 u: 查詢點 u 到根的路徑上第一個黑點的位置。

Analysis:


動態樹(8.7s +-
樹狀數組維護 DFS 序(7.2s +-

External link:

http://www.spoj.pl/problems/QTREE3/
http://hi.baidu.com/jollwish/blog/item/1e31b02e6d1f792f1f30891a.html