某岛

… : "…アッカリ~ン . .. . " .. .
September 4, 2011

【专题】动态树与树链剖分.. .

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=25242#overview

到此为止。。。我不能再被数据结构虐杀再摇篮中了。。
我不能再被数据结构虐杀再摇篮中了。。
我不能再被数据结构虐杀再摇篮中了。。
我不能再被数据结构虐杀再摇篮中了。。
….
— 9-3.

..
..

..
.
.

.
.

.

。。额。。动态树还有好多问题没有搞清楚啊。。。
。。再。。再回去读下论文了吧。。
— 9.4 。。

好像又理解了一点。。我好像错误的认为 树链剖分 和 动态树 只学习一个就可以了。。
这是多么的错误啊。。

只学树链剖分的下场我已经领会了。。。。只用动态树的话也是不行的。。 比如 IPSC 07 的 Rainbow 。。。

。。。感觉 动态树 里的 Access 操作各种理解上的不能啊。。。
只好明天去请教 fhq 了。。

—-9.5

。。今天 Debug 了一天伸展树。。T T。。

感觉伸展树。。还是 zkw (BST 拓展与伸展树 (Splay) 一日通
讲的最好啊!!。。T T 。你再去看一下他的那篇
统计的力量——线段树全接触
。。太强大了。。我以前怎么都没有意识到呢 T T

对于这个问题(伸展树这样旋转真的没关系么?)。。
以及 ( 贴两个比较短的splay )

(要解答这两个问题需要真正理解 伸展树的原文,
或者构造一组 N = 1,000 的退化数据。。)

额。。还有一道这么强大的题。。。T T
BZOJ 1146
—- 9.6

貌似不是旋转的问题.. .)
—- 9.7

.

Resources:

https://www.shuizilong.com/house/archives/2705
http://www.dxmtb.tk/blog/tag/qtree/
http://blog.imzzl.com/2010/07/643.html
http://hi.baidu.com/lemon_workshop/blog/item/9320152913ffeb2b5243c14f.html
http://crfish.blogbus.com/logs/61521366.html

http://fanhq666.blog.163.com/blog/static/819434262011179150889/

Exercises :

SPOJ 375. Query on a tree

URAL 1553. Caves and tunnels

BZOJ 2002. 弹飞绵羊

SPOJ 4155. OTOCI

IPSC 2009 Problem L. Let there be rainbows!

BZOJ 1095. [ZJOI2007]Hide 捉迷藏

BZOJ 1036. [ZJOI2008]树的统计Count

BZOJ 2325. [ZJOI2011]道馆之战

BZOJ 2243. [SDOI2011]染色

HDU 4010. Query on The Trees

ZJU 3522. Hide and seek