zcmimi's blog

arrow_backst表共1篇文章

avatar
zc
2020-10-29 16:00:01

查看原题

点击跳转

可以想到用并查集维护连通块(需要数字相同区域)个数

答案就是9*连通块个数

直接对每个点维护普通的并查集太慢了

由于并查集是可以合并的,我们可以使用倍增来合并

将一个点拆成\log n个点,分别代表从点i开始长度为2^k的子串

那么当我们处理两个区间相等的关系时,对区间做二进制拆分,拆成log个区间,分别并起来即可

最后再从上(大)往下(小)连边

1/1
Search
search