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

并查集维护每个水池的左右边界+前缀和

#include<bits/stdc++.h>
using namespace std;
using ld=long double;
using pii=pair<int,int>;
#define endl "\n"
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    vector<ld> pre(n+1);
    vector<pii> lr(n+1);
    pre[0]=0;
    for(int i=1;i<=n;i++){
        ld x;cin>>x;
        pre[i]=pre[i-1]+x;
        lr[i].first=i;lr[i].second=i;
    }
    auto findl=[&](auto findl,int x)->int{
        if(lr[x].first!=x) lr[x].first=findl(findl,lr[x].first);
        return lr[x].first;
    };
    auto findr=[&](auto findr,int x)->int{
        if(lr[x].second!=x) lr[x].second=findr(findr,lr[x].second);
        return lr[x].second;
    };
    int op;
    while(m--){
        cin>>op;
        if(op==1){
            int l,r;cin>>l>>r;
            int rr=findr(findr,r);
            for(int i=l;i<=r;i++)
            {
                int ir=findr(findr,i);
                lr[ir].second=rr;
                i=ir;//跳到最右端
            }
            int ll=findl(findl,l);
            for(int i=r;i>=l;i--)
            {
                int il=findl(findl,i);
                lr[il].first=ll;
                i=il;//跳到最左端
            }
        }
        else if(op==2){
            int i;
            cin>>i;
            int ll=findl(findl,i);
            int rr=findr(findr,i);
            cout<<fixed<<setprecision(10)<<(pre[rr]-pre[ll-1])/(rr-ll+1)<<endl;
        }
        else ;
    }
}