[Water]水之数据结构专版

【数据结构】

Link-Cut-Tree && 树链剖分

[bzoj3083]
[bzoj3510]
树链剖分也可以进行子树的处理。。。如果树的形态不发生变化基本上就万能了。。。(来自sillycross的亮瞎狗眼技巧)
每次合并两棵树求重心。。启发式合并,将小树一个一个点插入大树,每一次大树的重心至多向新插入点的方向移动1,判断之。
[JDFZOJ Change]
有个n个节点的有根树(顶点标号1-n),根是1。
开始时每个节点的点权都是0。
接下来有q个操作,每个操作有以下两种:

  1. 形式是1 v x k,表示将v点点权加x,v的孩子点权加x - k,v的孩子的孩子点权加x - 2 * k,以此类推。
  2. 形式是2 v,此操作询问v点点权。你要输出v点点权模1000000007. 直接维护差分,利用上述亮瞎狗眼技巧就行了。

self-adjusting-top-tree

[bzoj3153]

Euler-Tour-Tree

可持久化数据结构

可持久化线段树:充分利用上一个版本的信息!对于当前版本只需新建个节点。(完结)
树状数组+可持久化线段树:(to be continued...)
[bzoj2653]
@
序列中位数:长度为N的序列,按照不降排序,则(0~n-1)a[N/2下取整]或是(1~n)a[N/2上取整]为中位数。
那么令,显然若f(x)>=0时,x<=中位数。
然后就二分,以Rmax(a,b)+Sum(b+1,c-1)+Lmax(c,d)为依据。
但是显然我们不能建立值域颗线段树,这样就主席树就可以了。
@
[bzoj1803]
@
多次询问有根树以i为根的子树权值第k大。
首先找出dfs序,这样就变成区间第k大了,直接水过。
另外,dfs序列长度只要n就足够了,不需要2n!
@
[bzoj2120]
[bzoj3236]
[bzoj3674]
@
同3673,可持久化并查集。考虑朴素需要O(nm)时空显然会爆掉。于是使用主席树,每进行一次操作就新建一个版本的根,由于比上个版本至多只变化一个数,只需新建O(logn)个节点,于是就可以了。不过这道题需要启发式合并。。。再用一颗主席树维护一下size就行了,道理相同。
@
[bzoj3670]
@
对长为len的串构造0~len这些节点,令i的父亲为next[i],事实上对i询问的是i到0的链上标号不超过(i/2)的节点数(不包括0,i)。那么我们使用主席树维护哪些点在链上(0,1),计算前缀[1,i]的答案时,版本i事实上是版本next[i]再把next[i]加入链中,答案就是在版本i为根的线段树中询问[1,i]和。当然,这样复杂度是,会被卡T_T.

事实上我们有做法。首先进行KMP预处理,同时递推计算出每个点到根的链长度。再进行第二次KMP,进行一些改动,匹配i时,若发现当前j长度超过(i/2),则继续沿next[]向上。若可以匹配到,显然答案就出来了。
有时间再写.
@
可持久化平衡树treap:
主要函数:

void copy(Node *&Now, Node *Last) {
        if (Last == null)
            Now = Last;
    else
            Now = Newnode(), *Now = *Last;
}

那么只要把原来的'Now=Last',全部换成copy(Now,Last)就行了。
/参考课件/
HN2014 mx
可持久化数据结构研究 clj

comments powered by Disqus