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

本题数据量较大，用并查集把移走挡板后联通的几个池子合并成一个连通块，求某个池子的蓄水量，只需向上找其祖宗的值和池子总数即可。（每个连通块中，编号大的池子为编号小的节点的父亲）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200010;
int p[N],sz[N];
double a[N];
int find(int x)//并查集
{
    if(p[x]!=x)p[x]=find(p[x]);
    return p[x];
}
void add(int u,int v)
{
    int pu=find(u),pv=find(v);
    if(u>v)swap(u,v);
    p[pu]=p[pv];//节点合并
    sz[pv]+=sz[pu];//连通块的数量累计到祖宗节点
    a[pv]+=a[pu];//水池总量累计到祖宗节点
}
signed main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        p[i]=i;
        sz[i]=1;
    }
    while(m--)
    {
        int op;
        cin>>op;
        if(op==1)
        {
            int l,r;
            cin>>l>>r;
            for(int i=find(l);i<r;i=find(i))//其祖宗节点向上连接即可
            {
                add(i,i+1);
            }
        }
        else
        {
            int q;
            cin>>q;
            int t=find(q);
            printf("%.10lf\n",a[t]/sz[t]);//祖宗节点的蓄水量除以此连通块的数量
        }
    }
    return 0;
}