主题

主题

 
   

非正统树分块

  • 扯淡

树分块,自然可以想到是在树上分块。

学了一个比较naive的想法,一种广为流传的树上分块,叫做非正统树分块。

这个名词是WerKeyTom_FTD大爷提出来的吧。过几天准备去学学他的正统树分块。

很久以前看过了,不过一直不太懂正统树分块的三个限制是怎么回事。然后先学了一下非正统树分块。


  • 思想

贪心。

从上面往下面开始分块。

如果一个节点的父亲的块还没有被填满,那就用把这个节点放到父亲所在的块中,否则就不放。

把块之间再建一棵树。


  • 一个例子

3720: Gty的妹子树

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=3720

Description

我曾在弦歌之中听过你,

檀板声碎,半出折子戏。

舞榭歌台被风吹去,

岁月深处尚有余音一缕……

Gty神(xian)犇(chong)从来不缺妹子……

他来到了一棵妹子树下,发现每个妹子有一个美丽度……

由于Gty很哲♂学,他只对美丽度大于某个值的妹子感兴趣。

他想知道某个子树中美丽度大于k的妹子个数。

某个妹子的美丽度可能发生变化……

树上可能会出现一只新的妹子……

维护一棵初始有n个节点的有根树(根节点为1),树上节点编号为1-n,每个点有一个权值wi。

支持以下操作:

0 u x          询问以u为根的子树中,严格大于x的值的个数。(u^=lastans,x^=lastans)

1 u x          把u节点的权值改成x。(u^=lastans,x^=lastans)

2 u x          添加一个编号为"当前树中节点数+1"的节点,其父节点为u,其权值为x。(u^=lastans,x^=lastans)

最始时lastans=0。

Input

输入第一行包括一个正整数n(1<=n<=30000),代表树上的初始节点数。

接下来n-1行,每行2个整数u,v,为树上的一条无向边。

任何时刻,树上的任何权值大于等于0,且两两不同。

接下来1行,包括n个整数wi,表示初始时每个节点的权值。

接下来1行,包括1个整数m(1<=m<=30000),表示操作总数。

接下来m行,每行包括三个整数 op,u,v:

op,u,v的含义见题目描述。

保证题目涉及的所有数在int内。

Output

对每个op=0,输出一行,包括一个整数,意义见题目描述。

Sample Input

2

1 2

10 20

1

0 1 5

Sample Output

2


个人解法:

自然,如果是序列上的,我们直接分块,块内维护有序数组,套二分即可。

时间复杂度为O(nsqrt(n)loign)。log为常数。

那么在这里我们把树分块了,按照类似的方法查询就好了。


  • 实现

修改:

我们找到它所在的块,暴力修改与重构。这和序列上的没有什么太大的差别。

查询:

首先,当前节点p所在的块,自然是暴力枚举最好了。由于块的大小为sqrt(n),所以这一部分的复杂度不会很大。

接下来,对于与p不在同一个块的子树部分,我们就可以把它当做一整块来查询。这一部分的复杂度是有块数来决定的。

代码如下:

https://code.csdn.net/snippets/2214299

关于此题的另一个想法:

我们发现查询子树是可以使用DFS序的。于是我们可以尝试维护子树。

那么我们需要维护一个点在DFS序中的位置,以及子树大小Size。

这些部分在插入节点的时候都会变化。

关于DFS序中的位置,我们只需要一个支持插入的有序数组即可。Splay可以做到这一点。

关于子树大小Size,我们发现——如果插入一个节点,当前节点到根的Size都会+1。那么我们需要一种支持加边+区间加+单点查询的玩意。显然就会想到LCT。

然而修改操作对上面两个玩意均无任何影响。

做完之后,我们剩余的任务就是在一个序列上插入+修改+查询区间大于k的数字。

这个自然可以用块状链表实现。

时间复杂度变为O(nsqrt(n)logn)

代码如下:

https://code.csdn.net/snippets/2215237


 

  • 为什么叫非正统树分块

调试的时候就不难发现,这个玩意的块的个数挺大的。

比方说一张菊花图,块的个数就会变为O(n)级别。所以用非正统树分块的话,自然需要把块的个数范围调到O(n)。

(为什么还要学这玩意呢?)

(出题人自然不会每张图都是菊花图——再者,菊花图(近似菊花图)又可以通过暴力来处理。通过对点的度数的判断可以权衡复杂度)

正统树分块是可以保证树块的大小的。

 
 
评论