题解 | #小苯的蓄水池（hard）#

区间集合管理 (Interval Management System)

针对频繁的区间合并与点查询，最理想的策略是维护一组不相交的连通区间（Disjoint Intervals）。

核心范式：基于有序集合的区间收缩

我们选择使用一个支持快速查找和维护有序性的数据结构（如 C++ 中的 std::set 或平衡树）来存储当前的连通块。每个块定义为一个三元组 $(L, R, S)$ ，其中：

$L$ : 区间左端点。
$R$ : 区间右端点。
$S$ : 该区间内的总水量（和）。

为什么选择此方案？

分摊复杂度分析：虽然单次合并操作 $1$ 可能涉及多个现有区间的删除，但每个区间在整个生命周期中只会被创建一次、删除一次。因此， $m$ 次操作后的总删除次数上限为 $O(n+m)$ 。每次查找边界的复杂度为 $O(\log n)$ ，整体分摊复杂度为 $O((n+m) \log n)$ 。
空间高效：空间复杂度与区间数量成正比，最坏情况下为 $O(n)$ 。
查询直观：点查询 $i$ 转化为在有序集合中定位包含 $i$ 的区间 $[L, R]$ ，其结果即为 $S / (R - L + 1)$ 。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Pool {
    int l;
    int r;
    mutable ll v;

    bool operator<(const Pool& o) const {
        return l < o.l;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, m;
    cin >> n >> m;

    set<Pool> pool;
    for (int i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        pool.insert({i, i, a});
    }

    while (m--) {
        int op;
        cin >> op;

        if (op == 1) {
            int ql, qr;
            cin >> ql >> qr;

            auto it = pool.lower_bound({ql, 0, 0});
            if (it != pool.begin()) {
                auto prev_it = prev(it);
                if (prev_it->r >= ql) {
                    it = prev_it;
                }
            }

            ll total = 0;
            int nl = -1;
            int nr = -1;

            while (it != pool.end() && it->l <= qr) {
                if (nl == -1)
                    nl = it->l;
                nr = max(nr, it->r);
                total += it->v;

                it = pool.erase(it);
            }

            if (nl != -1) {
                pool.insert({nl, nr, total});
            }
        } else if (op == 2) {
            int pos;
            cin >> pos;

            auto it = pool.upper_bound({pos, 0, 0});
            it = prev(it);

            double ans = (double)it->v / (it->r - it->l + 1);
            cout << fixed << setprecision(10) << ans << endl;
        }
    }
}

复杂度分析

维度	复杂度	说明
时间复杂度 (合并)	$O(\log n)$ (分摊)	单次操作可能 $O(k \log n)$ ，但总删除次数受限，分摊后极低。
时间复杂度 (查询)	$O(\log n)$	典型的二分查找复杂度。
空间复杂度	$O(n)$	存储区间三元组所需空间。