0%

loj 2048. 「HNOI2016」最小公倍数

loj 2048. 「HNOI2016」最小公倍数

给一个$n$个点$m$条边的无向图,每条边有属性$a_i,b_i$.有$Q$次询问,每次询问给出$u,v,A,B$,你需要回答从点$u$到点$v$是否存在一条路径$P$(不要求是简单路径)满足 $\max_{e\in P}\{a_e\}=A$且$\max_{e\in P}\{b_e\}=B$

$n,q\le 5\times 10^4,m\le 10^5.$

My solution:

考虑如果我们得到了图$G(A,B)=(V,\{e|a_e\le A,b_e\le B\})$,如何处理询问。维护一个并查集,将$G(A,B)$中所有边加入并维护连通块的$a_e$最大值和$b_e$最大值。

【判定】: $u,v$存在合法路径 $\Leftrightarrow $ $u,v$在$G(A,B)$中连通,且所在连通块$a_e$最大值为$A$,$b_e$最大值为$B$.

所以就是如何得到图$G(A,B)$了。大概就是要实现”不强制在线的二维可持久化并查集”。

如果不考虑$b$ 直接上可持久化并查集啊 还是容易处理的:按照套路,将询问离线,将边和询问一起以$a$为关键字排升序($a$相同时边优先)。依次考虑之,若是边就在并查集上合并,若是询问,此时的并查集中已包含了所有$a_e\le A$的边,使用【判定】即可。

现在有了$b$.将边复制一份,按$b$排序并分块,每$\sqrt m$条边一个块(注意必须是按边数分块,按$b$的值域分不能保证每个块内的边数为$\sqrt m$)。每个块分别维护一个并查集,第$i$个块的并查集存有前$i-1$个块中所有$b_e\le bmin_{i}$,$bmin_i$表示第$i$个块中$b$的最小值。

加入一条边时,找到其所在块$i$,并标记已被加入。将其加入所有$j>i$的块的并查集中。对于询问,找到其对应块(最大的$i$满足$bmin_i\ge B$),并将该块中所有$b_e\le B$的$e$也都在该块的并查集上合并,我们就得到了所要的图$G(A,B)$,【判定】即可.然后将这些操作回退。

复杂度$\mathcal O((m+Q)\sqrt m\log n)$

My code (不知道为什么明明复杂度一样却比最优解慢了7倍)