可撤销性并查集:
可撤销性并查集能够撤销最后几次的修改操作,而不能撤销若干不连续的操作 具体是怎么做到的,我们用到的是放弃路径压缩,使用启发式合并的并查集,简而言之就是小的块挂到大的块上面,这样的话每个点每查询一次父亲,块至少翻倍,这样每次查询的复杂度为log(n)
每次撤销时,从栈弹出若干个操作,fx是大块.fy是小块,我们把siz[fx]-=siz[fy],并复原f[fy]=fy,如果是要对单独节点产生某个值的化,我们可以用到懒标记,当然要在每次合并完了后执行tag[fy]-=tag[fx],这是为了抵消fy本来就不该有的部分
线段树分治:
其实更应该叫时间轴线段树,对于某个段[l,r],我们如果要加一条边,那么会在线段树里面不超过log(n)个节点中加上边,之后dfs遍历线段树,先记录当前栈的大小now,我们把这个节点存在的东西merge掉,在递归完成后把栈弹出至siz==now,这样的话总体时间复杂度nlognlogn,nlogn是因为,有n个时间段,并且每个时间段在线段树中对应的点<=logn,所以会合并nlogn次,还有个log是find的
习题:
京公网安备 11010502036488号