题解 | #小苯的蓄水池#

首先因为隔板的存在，所以整个水池开始是一坨一坨的，一共有 坨。

操作 就是把所有与 有交集的坨坨拿来进行合并，合并结果为总水量除以总池子数。

考虑用 set 维护，这样查询就是严格 级别的，我们来分析修改操作。

由于每次合并坨数都会减少 ，所以最多合并 次，均摊下来总复杂度为 ，这样总复杂度就是 + 。足以通过此题。

the code：

#include <bits/stdc++.h>

#define L(i, a, b) for(int i = (a); i <= (b); i++)
#define R(i, a, b) for(int i = (a); i >= (b); i--)
#define ll long long

using namespace std;

const int N = 500000 + 10;

int n, q; double a[N];

struct Node {
	int l, r; double w;
	bool operator < (const Node &T) const {
		return l < T.l;
	}
};

set<Node> S;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);  cout.tie(0);
	cin >> n >> q;
	L(i, 1, n) cin >> a[i], S.insert({i, i, a[i]});
	cout << fixed << setprecision(8);
	while(q--) {
		int op, l, r;
		cin >> op;
		if(op == 1) {
			cin >> l >> r;
			auto it = S.upper_bound({l, 0});
			--it;
			vector<set<Node>::iterator> vec;
			double sum = 0; int R = r, L = it->l;
			while(it != S.end() && it->l <= r) {
				vec.push_back(it);
				sum += it->w * (it->r - it->l + 1);
				R = max(R, it->r);
				it++;
			}
			for(auto x : vec) S.erase(x);
			S.insert({L, R, sum / (R - L + 1)});
		}
		else {
			cin >> l;
			auto it = S.upper_bound({l, 0});
			it--;
			cout << it->w << '\n';
		}
	}
	return 0;
}