P3295 [SCOI2016] 萌萌哒 题解

· · 题解

P3295 [SCOI2016] 萌萌哒 题解

solution

朴素的想法中，若确定两个位置相同，则将它们归为一块，最后有 cnt 个块，答案就为 9 \times 10^{cnt-1}（最高位不为零）。这个合并块的操作由并查集完成。时间复杂度 \Theta(n^2\times\alpha(n))。（\alpha(n) 是路径压缩并查集复杂度，以下略写）。

考虑优化这个算法，这个算法的合并操作是 \Theta(n)，最终查询是 \Theta(1) 的，不平衡。考虑使用区间拆分的方法平衡复杂度。

观察到并查集的合并是允许重复的，一对点连两遍不影响正确性，于是采用ST表的方法，令 (i,j) 表示i\sim i+2^j-1的区间。

令 len=r_1-l_1+1, k=\lfloor \log_2 len\rfloor。两个区间连边即为：

(l_1,k)\leftrightarrow (l_2,k) (r_1-2^k+1,k)\leftrightarrow (r_2-2^k+1,k)

之后就是拆分区间，把大区间的连边关系下传到小区间。令 (i,j) 为大区间，(y,j) 为关联的区间（根据上面的连边，只有相同的层才会连边）。

(i,j-1)\leftrightarrow (y,j-1) (i+2^{j-1},j-1) \leftrightarrow (y+2^{j-1},j-1)

最后统计第 0 层的联通块个数，计算答案。

code

注意连边顺序，一层一层连边，而不是直接往下连。