P3295

题目链接 点击打开链接 题目解法 暴力并查集 \(merge\) 肯定不可行 对于限制是 \(O(n^2)\) 的，查询却是 \(O(n)\)，所以考虑均衡复杂度 可以用倍增的思想求解 令 \(fa_{i,j}\) 为 \([i,i+2^j-1]\) 的并查集数组，记录的是祖先的下标 这样限制不难做 ......