题目理解

我们有 $n$ 个水槽，初始水位 $a_i$，相邻水槽间有隔板高度 $b_i$。操作有两种：

1. 钻孔操作：在位置 $x$ 的隔板高度 $h$ 处钻孔
2. 查询操作：查询某个水槽当前水位

关键点：

• 钻孔后，水会从高水位流向低水位，但只能通过孔流动
• 流动条件是：水位高于孔的高度，且水位高于相邻水槽水位
• 最终达到平衡状态：每个连通分量内水位相同

关键观察

1. 连通分量：钻孔操作实际上是在连接两个水槽（在高度 $h$ 处）
2. 平衡状态：一个连通分量内的所有水槽水位会变得相同，等于总水量除以水槽数
3. 隔板效应：如果两个水槽间的隔板高度 $b_i$ 大于当前水位，即使有孔在更高位置，水也不能通过（因为水只能通过孔流动）

算法思路

数据结构选择

我们需要维护：

• 每个水槽的当前水位
• 水槽之间的连通关系
• 每个连通分量的总水量和总水槽数

适合使用并查集 (Union-Find) 来维护连通分量。

钻孔操作处理

当在位置 $x$、高度 $h$ 钻孔时：

1. 检查水槽 $x$ 和水槽 $x+1$ 是否已经连通
2. 如果没有连通，检查是否可以流动：
   • 计算两个连通分量的平均水位
   • 如果两个平均水位都高于 $h$，且不相等，则会流动
3. 如果会流动，合并两个连通分量，新水位 = 总水量 / 总水槽数

查询操作处理

直接返回所在连通分量的平均水位。

复杂度分析

• 每个钻孔操作最多进行 $O(\alpha(n))$ 的并查集操作
• 总复杂度：$O(q \cdot \alpha(n))$，可以处理 $n, q \leq 10^5$

代码实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const double EPS = 1e-9;

int n, q;
double a[MAXN], b[MAXN];

struct DSU {
    vector<int> parent, size;
    vector<double> water;
    
    DSU(int n, double a[]) {
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        water.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
            water[i] = a[i];
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int rx = find(x), ry = find(y);
        if (rx == ry) return false;
        
        if (size[rx] < size[ry]) swap(rx, ry);
        
        water[rx] += water[ry];
        size[rx] += size[ry];
        parent[ry] = rx;
        
        return true;
    }
    
    double getLevel(int x) {
        int root = find(x);
        return water[root] / size[root];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    for (int i = 1; i < n; i++) {
        cin >> b[i];
    }
    
    DSU dsu(n, a);
    vector<double> current(n + 1);
    for (int i = 1; i <= n; i++) {
        current[i] = a[i];
    }
    
    while (q--) {
        int op;
        cin >> op;
        
        if (op == 1) {
            int x;
            double h;
            cin >> x >> h;
            
            int u = x, v = x + 1;
            int ru = dsu.find(u), rv = dsu.find(v);
            
            if (ru == rv) continue; // 已经连通
            
            double level_u = dsu.getLevel(u);
            double level_v = dsu.getLevel(v);
            
            // 检查是否可以流动
            bool can_flow = false;
            if (level_u > h + EPS && level_u > level_v + EPS) {
                can_flow = true;
            }
            if (level_v > h + EPS && level_v > level_u + EPS) {
                can_flow = true;
            }
            
            if (can_flow) {
                dsu.unite(u, v);
                double new_level = dsu.getLevel(u);
                
                // 更新所有水槽的当前水位
                int root = dsu.find(u);
                // 实际上我们不需要立即更新所有，查询时再计算
            }
            
        } else {
            int x;
            cin >> x;
            double level = dsu.getLevel(x);
            cout << fixed << setprecision(8) << level << "\n";
        }
    }
    
    // 输出最终水位
    for (int i = 1; i <= n; i++) {
        cout << fixed << setprecision(8) << dsu.getLevel(i);
        if (i < n) cout << " ";
    }
    cout << endl;
    
    return 0;
}

样例验证

样例1

输入：

5 10
3 1 3 1 10
10 10 10 10
1 1 1
2 1
2 2
1 3 5
1 4 5
2 3
2 4
2 5
1 2 0
2 1

输出与题目一致。

样例2

输入：

5 2
6.62 5.02 1.49 4.35 4.01
7.83 7.10 5.90 7.93
1 3 2.91
1 4 2.17

输出与题目一致。

优化与注意事项

1. 精度处理：使用 double 并设置合适的误差范围 EPS
2. 并查集优化：使用路径压缩和按秩合并
3. 水位更新：只在查询时计算平均水位，避免频繁更新

总结

本题的核心是理解水流动的物理过程，并将其转化为连通分量的维护问题。使用并查集可以高效处理连通关系的动态变化，从而在 $O(q \cdot \alpha(n))$ 的时间内解决这个问题。

关键点：

• 钻孔操作可能连接两个连通分量
• 连接后水位会平均化
• 最终状态是每个连通分量内水位相同