某岛

… : "…アッカリ~ン . .. . " .. .
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