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

使用并查集进行合并，每一次的（l,r)合并从左到右更新根节点（指向r），由于不会重复拆板子，所以遍历的合并方法是可行的。

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

int n;
vector<ll> sum; // ll sum[n+2];
vector<int> cnt;
vector<int> fa; // int fa[n+2];

int find(int x)
{
    if(fa[x]==x) return x;
    else
    {
        fa[x] = find(fa[x]);
        return fa[x];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int m;
    cin >> n >> m;
    sum.resize(n+2);
    fa.resize(n+2);
    cnt.resize(n+2);
    vector<int> water(n+2,0);
    for(int i = 1; i <= n; i++)
    {
        cin >> water[i];
    }
    for(int i = 1; i <= n; i++)
    {
        fa[i] = i;
        sum[i] = water[i];
        cnt[i] = 1;
    }
    for(int i = 0; i < m; i++)
    {
        int op;
        cin >> op;
        if(op==1)
        {
            int l,r;
            cin >> l >> r;
            int cur=find(l);
            while(cur<r)
            {
                int next_root = find(cur+1);
                fa[cur] = next_root;
                sum[next_root] +=sum[cur];
                cnt[next_root]+=cnt[cur];
                cur = next_root;
            }
        }
        if(op==2)
        {
            int i;
            cin >> i;
            int root = find(i);
            double ans = (double)sum[root] / (double)cnt[root];
            cout << fixed << setprecision(10) << ans << endl;
        }
    }
}