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

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
double a[N];
int fa[N];
int sz[N];
double avg[N];
int n,m;


int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}


void merge(int x,int y)
{
    int fx = find(x);
    int fy = find(y);
    if(fx==fy)return ;

    if(fx<fy)swap(fx,fy);
    
    avg[fx] = ((double)sz[fx]*avg[fx]+(double)sz[fy]*avg[fy])/(double)(sz[fx]+sz[fy]);
    sz[fx]+=sz[fy];
    fa[fy]=fx;
}


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

    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        fa[i]=i;
        sz[i]=1;
        avg[i]=a[i];
    }

    for(int i=1;i<=m;i++)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r;
            cin>>l>>r;
            int L = l;
            int R = r;
            int ans = find(l);
            while(find(ans)!=find(r))
            {
                merge(ans,ans+1);
                ans=find(ans);
            }
        }
        else 
        {
            int x;
            cin>>x;
            printf("%.7lf\n",avg[find(x)]);
        }
    }

}

并查集