zcmimi's blog

arrow_back回滚莫队共5篇文章

avatar
zcmimi
2020-07-11 07:23:00

有一类普通莫队不可解的问题就是在转移区间过程中,可能出现删点或加点操作其中之一无法实现的问题,这时可以使用回滚莫队算法

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

题意:

给出n个点m条边的无向图,每条边u\leftrightarrow v有两个权值a,b

q个询问,给出u,v,A,Bu,v间是否存在路径\max\{a\}=A\max\{b\}=B

先考虑最暴力的做法:

把所有符合条件的边(a\le A,b\le B)添加到并查集,

然后判断最大值是不是A,Bu,v是否连通

接着对边排序、回滚莫队,使用按秩合并并查集(可撤销并查集)

m条边按a进行排序

对询问按b进行排序

m条边进行分块

对每个块处理符合a大于等于该块\max\{a\}的询问

把当前块前面的点按照b排序(使b单调递增)

开始处理询问:

当前块前面的点的b是单调递增的,而a一定符合条件 ,所以可以一直右移指针添加符合条件的边

然后枚举块中的边,添加符合当前询问的边,得到当前询问答案,回滚,删掉当前询问添加的边

下一个询问

处理完当前块后,暴力清空并查集

分块大小为\sqrt{m\log n}时复杂度最优

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

这题可以算是回滚莫队板子题

S为前缀和

假设区间[l,r]区间和为0,那么S_r-S_{1-1}=0

如果使用莫队算法的话,容易想到:

用桶记录某个前缀和出现的最大/最小位置,加点操作就很容易维护答案

但这样的话删点操作就有点难实现了

可以使用回滚莫队

回滚莫队是一种只添加不删除的莫队,实现如下:

首先对原序列进行分块,并对询问按照如下的方式排序:以左端点所在的块升序为第一关键字,以右端点升序为第二关键字

枚举当前要处理的块,处理所有左端点在该块内的询问,

设当前块右端为R,左指针移动到R+1,右指针移动到R.

若询问两端在同一块内,那么暴力枚举统计即可

  1. 由于左端点在同一块内,右端点单调递增

    不断右移右指针到当前询问右端点,并加点更新总答案

    (每个块右端点总位移不超过n)

  2. 不断左移左指针到当前询问左端点,并加点更新当前询问答案

    然后将左端点回滚到R+1,撤销加点操作对桶的影响

    (每次回滚左端点位移不超过\sqrt n)

继续处理下一个询问

总复杂度O(n\sqrt n),实测跑的飞快

请配合代码理解,注意细节

avatar
zc
2020-07-18 11:27:00
查看原题

点击跳转

1/1
Search
search