这题可以把“拿掉挡板”理解成:把两个相邻水池连起来。 连在一起的整段水池会混合成同一个水量,这个水量就是: 这段总水量 / 这段水池个数 所以我们要维护两个东西: 哪些水池已经连成一段(连通块) 每段的“总水量”和“长度” 这正好是并查集能做的: fa 维护连通块 sm 维护块内总水量 sz 维护块大小 查询 2 i 时,输出 sm[root(i)] / sz[root(i)] 难点在操作 1 l r: 它要删除区间 [l,r] 里所有挡板,也就是把边 (l,l+1),(l+1,l+2),...,(r-1,r) 全部连起来。 如果每次都暴力扫,会超时。 这里再加一个“跳指针并查集”...