牛客周赛 Round 66 E题 小苯的蓄水池（hard）

原题链接

https://ac.nowcoder.com/acm/contest/93847/E

题面

解题思路

拆除挡板相当于将两个区间进行合并，所以可以想到使用并查集来解决本题。
我们可以把每个区间的所有点的祖先结点都赋值为该区间最右端点i，在最开始的情况下每两个相邻的蓄水池之间都有一个隔板，所以我们初始化并查集所有的顶点i的根节点为他们本身。假设我们现在要拆除i和i+1之间的挡板，在我们这个并查集中也就相当于合并i和i+1的祖先结点（即合并i和i+1各自所在的这两个集合）。
所以我们如果要拆除给定区间[l,r]内的所有挡板，体现在并查集上，就等价于把[l,r]从左往右进行并查集的合并，合并的同时将操作里涉及的区间进行统计。详细见代码。

时间复杂度:O(n)

代码（CPP）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define endl "\n"
const int maxn = 2e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3fLL;
double a[maxn];
int cnt[maxn];
int father[maxn];
int n;

void Init() {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        cnt[i] = 1;
    }
}

int FindFather(int x) {
    if (x == father[x])
        return x;
    return father[x] = FindFather(father[x]);
}

void Merge(int u, int v) {
    int faU = FindFather(u);
    int faV = FindFather(v);
    if (faU != faV) {
        father[faU] = faV;      // 把每个区间的所有点的祖先结点都赋值为该区间最右端点i
        cnt[faV] += cnt[faU];
        a[faV] += a[faU];
    }
}

void solve() {
    int m;
    cin >> n >> m;
    Init();
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    while (m--) {
        int op;
        cin >> op;
        if (op == 1) {
            int l, r;
            cin >> l >> r;
            for (int i = l; i < r;) {
                Merge(i, i + 1);
                i = FindFather(i);
            }
        } else {
            int x;
            cin >> x;
            int faX = FindFather(x);
            cout << a[faX] / cnt[faX] << endl;
        }
    }
}

int main() {
//     freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    solve();
    return 0;
}