WC2014 UOJ55 紫荆花之恋

有生之年终于A掉这题了！

陈老师的数据结构题全都是神题...

题意不说了...

以下是Recursion这个逗逼的卡评测机记录：

题解：

首先我们把[tex]dist(i,j)\leq r_i+r_j[/tex]变形为[tex]dist(i,p)-r_i\leq r_j-dist(j,p)[/tex]，其中[tex]p=LCA(i,j)[/tex]。

我们考虑树分治，建出点分治的每一层结构。对于每一层，我们对每个节点开一个平衡树记录子树的所有[tex]dist(i,p)-r_i[/tex]。查询的时候依次统计分治结构的每一层。注意这样可能会算重，我们额外开一个平衡树记录再向上一层的值，每一层减掉可以在上一层统计的答案。

动态维护点分治结构的时候我们利用替罪羊树的思想，设一个阈值，在树不符合子树大小平衡的时候拍扁重建，这样每个节点只会在[tex]\log[/tex]层里出现。

其实写起来就是细节稍微多一些长度并不长嘛...

不过拍扁重建的时候稍不注意就会mle+tle...我调了半天参还是没过...最后抄了一个内存池才过...感觉内存池还是挺有用的...

动态树分治真是个强大的算法啊...还有替罪羊树思想感觉也好神...