P3295 [SCOI2016] 萌萌哒 题解

· · 题解

首先，将 [l_1,r_1]=[l_2,r_2] 转化为 \forall i\in[0,r_1-l_1),s{l_1+i}=s{l_2+i}。

注意到这个等式可以用并查集维护，令集合个数为 k，答案就是 9\times10^{k-1}。时间复杂度最坏是 O(n^2)，考虑优化。

首先容易想到将小的查询合并，从而得到大的查询块。所以考虑分块，令块长为 T。

注意到如果直接对序列分块，每次查询散落在块中的不同位置，整块会被分割，直接维护整块较难。

所以我们可以略微修改一下我们分块的做法：从每个点都扩展 T 个元素作为一个块，可以考虑整块和散块都开一个并查集维护。

那么此时我们可以直接从每个询问的左端点开始往右跳整块，整块之间合并，剩下的小块之间也要合并，时间复杂度为 O(\frac{nm}{T})。

注意到一个点所在的散块是一个集合，在对应的整块中还有 T 个集合。

我们可以直接合并一个元素和它所在的整块中所对应的元素所在的集合，时间复杂度 O(nT)。