倍增

第一次做到这种倍增题，有点有趣 首先区间内的每个点对应相等用并查集维护一下就好了，显然最后的答案就是（并查集个数为 $t$） $9 \cdot 10^{t - 1}$ 当然这样会造成 $O (n^2)$ 的复杂度，那么通过倍增来优化，即将区间二进制拆分，然后每次将 $[l_1, l_1 + 2^k - 1]$ 与 $[l_2, l_2 +2^k - 1]$ 合并，其中 $k$ 为二进制拆分结果所得幂次的部分，那么这样修改就变成 $O (n \log n)$ 了 对于查询，显然是不能直接查询了，那么就通过由大区间到小区间的传递（即将大区间拆分为左右两段，然后分别与之祖先拆分得左右两段合并）来将信息转移到最小的（即以点为单位的）区间段上 那么最后即 $O (n)$ 查询并查集个数即可 故该倍增整体思想即为：将以点为单位处理改为以幂次区间段为单位处理 $\rightarrow$ 将幂次区间段的信息转移到小区间直至单位区间 $\rightarrow$ 答案处理 代码12345678910111213141516171819202122232425262728293031323334353637 ...