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

首先看到这一题的时候不难想到使用'并查集'来维护不同水池的联通，但是后来发现我们合并水池之后水位可能会出现变化，所以尝试给并查集加入总量记载的同时再加入合并数量的计算，最后，我们发现联通水池时一旦板子被撤掉就不需要再管他了，而且题目可能在联通方面会有很大的时间消耗，正好有并查集在题目中间，微调一下加入链式并查集的思想，用来维护板子的存在即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define endl '\n'
#define pb push_back
#define ull unsigned long long
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define vii vector<vector<int>>
#define fi first
#define se second
#define vs vector<string>
#define eb emplace_back
#define in insert
#define pf push_front
#define sep "================"
#define ios                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);
const int inf = 2e18 + 9;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
typedef pair<int, int> pll;
typedef long double db;
inline void pt(int x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        pt(x / 10);
    putchar(x % 10 + '0');
}
inline void print(int x) { pt(x), puts(""); }
inline void print(pll x) { pt(x.fi), putchar(' '), pt(x.se), putchar('\n'); }
inline void print(vi &vec)
{
    for (const auto t : vec)
        pt(t), putchar(' ');
    puts("");
}
inline void print(vector<pll> &vec)
{
    puts(sep);
    for (const auto v : vec)
    {
        print(v);
    }
    puts(sep);
}
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; };
inline int qsm(int a, int b, int mod) ;
inline int lem(int a, int b) { return a * b / (gcd(a, b)); }
vii mul(vii &h1, vii h2)
{
    int a1 = h1.size();
    int a2 = h2[0].size();
    int a3 = h1[0].size();
    vii ans(a1, vi(a2, 0));
    for (int i = 0; i < a1; i++)
    {
        for (int j = 0; j < a2; j++)
        {
            for (int k = 0; k < a3; k++)
            {
                ans[i][j] = (ans[i][j] + (__int128)h1[i][k] * h2[k][j]);
            }
        }
    }
    return ans;
}
inline int read()
{
    int x = 0;
    short f = 1;
    char c = getchar();
    while ((c < '0' || c > '9') && c != '-')
        c = getchar();
    if (c == '-')
        f = -1, c = getchar();
    while (c >= '0' && c <= '9')
        x = x * 10 + c - '0', c = getchar();
    x *= f;
    return x;
}
int per(int n, int m)
{
    if (m == 0)
    {
        return 1;
    }
    int result = 1;
    for (int i = 0; i < m; ++i)
    {
        result *= (n - i);
    }
    return result;
}
void C()
{
    const int N = 200005 + 10;
    int inv[N];
    int jie[N];
    jie[0] = 1;
    for (int i = 1; i < N; i++)
    {
        jie[i] = jie[i - 1] * i % mod1;
    }
    inv[N - 1] = qsm(jie[N - 1], mod1, mod1 - 2);
    for (int i = N - 2; i >= 0; i--)
    {
        inv[i] = inv[i + 1] * (i + 1) % mod1;
    }
}
struct dsu
{
    vi pa , sz , num , fa ;
    dsu(int n) : pa(n) , sz(n , 0) , num(n , 1) , fa(n) {iota(all(pa) , 0);iota(all(fa) , 0);}
    int find(int x)
    {
        return pa[x] == x ? x : pa[x] = find(pa[x]) ;
    }
    int find1(int x)
    {
        return fa[x] == x ? x : fa[x] = find1(fa[x]) ; 
    }
    void unite(int x,  int y)
    {
        x = find(x) ;
        y = find(y) ; 
        if(x == y)return ;
        if(x > y) swap(x, y); 
        pa[x] = y; 
        sz[y] += sz[x];
        num[y] += num[x];
    }

};
void work()
{
    int n = read() , m = read() ;
    dsu tree(n + 2) ;
    for(int i = 1 ; i <= n ; i++)tree.sz[i] = read() ;
    while(m--)
    {
        int op = read() ;
        if(op == 1)
        {
            int l = read() ;
            int r = read() ; 
            for(int i = tree.find1(l) ; i < r ; i = tree.find1(i))
            {
                tree.unite(i , i + 1);
                tree.fa[i] = tree.find1(i + 1) ;
            }
        }
        else 
        {
            int i = read() ;
            i = tree.find(i) ;
            double ans = (tree.sz[i] * 1.000 / tree.num[i]) ;
            printf("%.10lf\n" , ans) ;
        }
    }
}
signed main()
{
    work();
    return 0;
}
inline int qsm(int a, int b, int mod)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return res % mod;
}