解题思路

核心思想

• 每个 tab 表示一个静态连通分量。

• 维护两个哈希表：

  • sz[tab]：该组试管数量。
  • sum[tab]：该组当前总水量。

这样，三种操作就转化为对哈希表的增减查：

• 加水：sum[tab[a]] += b
• 抽水：sum[tab[a]] -= b
• 查询：输出 sum[tab[a]] / sz[tab[a]]

复杂度分析

• 建立 sz：O(n)
• 每次操作：哈希表查找 O(1) 平均
• 总复杂度：O(n + m)
• 空间复杂度：O(n)

Python

import sys

data = sys.stdin.read().strip().split()
it = iter(data)
try:
    n = int(next(it)); m = int(next(it))
except StopIteration:
    sys.exit(0)

tab = [0]*(n+1)
sz = {}
sumv = {}

# 读tab并统计每个组大小
for i in range(1, n+1):
    t = int(next(it))
    tab[i] = t
    if t not in sz:
        sz[t] = 0
        sumv[t] = 0.0
    sz[t] += 1

out = []
for _ in range(m):
    o = int(next(it))
    if o == 1:
        a = int(next(it)); b = float(next(it))
        sumv[tab[a]] += b                 # 加水
    elif o == 2:
        a = int(next(it)); b = float(next(it))
        sumv[tab[a]] -= b                 # 抽水
    else:  # o == 3
        a = int(next(it))
        t = tab[a]
        out.append(f"{sumv[t]/sz[t]:.6f}")

sys.stdout.write("\n".join(out))

Java 实现

// 使用HashMap存储每个tab的组大小和总水量

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder all = new StringBuilder();
        String line;
        while((line = br.readLine()) != null) all.append(line).append(' ');
        StringTokenizer st = new StringTokenizer(all.toString());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] tab = new int[n+1];
        HashMap<Integer,Integer> sz = new HashMap<>();
        HashMap<Integer,Double> sum = new HashMap<>();

        for(int i=1;i<=n;i++){
            int t = Integer.parseInt(st.nextToken());
            tab[i] = t;
            sz.put(t, sz.getOrDefault(t,0)+1);
            sum.putIfAbsent(t, 0.0);
        }

        StringBuilder out = new StringBuilder();
        for(int i=0;i<m;i++){
            int o = Integer.parseInt(st.nextToken());
            if(o==1){
                int a = Integer.parseInt(st.nextToken());
                double b = Double.parseDouble(st.nextToken());
                int t = tab[a];
                sum.put(t, sum.get(t)+b);
            }else if(o==2){
                int a = Integer.parseInt(st.nextToken());
                double b = Double.parseDouble(st.nextToken());
                int t = tab[a];
                sum.put(t, sum.get(t)-b);
            }else{
                int a = Integer.parseInt(st.nextToken());
                int t = tab[a];
                double ans = sum.get(t)/sz.get(t);
                out.append(String.format(java.util.Locale.US, "%.6f\n", ans));
            }
        }
        System.out.print(out.toString());
    }
}

C++

// 使用unordered_map存储每个tab的组大小和总水量
#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m;
    if(!(cin>>n>>m)) return 0;

    vector<int> tab(n+1);
    unordered_map<int,int> sz;
    unordered_map<int,double> sum;

    for(int i=1;i<=n;i++){
        cin>>tab[i];
        sz[tab[i]]++;
        if(!sum.count(tab[i])) sum[tab[i]]=0.0;
    }

    cout.setf(ios::fixed);
    cout<<setprecision(6);

    for(int i=0;i<m;i++){
        int o; cin>>o;
        if(o==1){
            int a; double b; cin>>a>>b;
            sum[tab[a]] += b;
        }else if(o==2){
            int a; double b; cin>>a>>b;
            sum[tab[a]] -= b;
        }else{
            int a; cin>>a;
            int t = tab[a];
            cout<<sum[t]/sz[t]<<"\n";
        }
    }
    return 0;
}

题目内容

牛牛最近学习了连通器原理：在连通器中装有同种液体，当连通器中液体不流动时，各容器中液面总保持相平。如下图所示，四个底部连通的容器液面都是相平的。

牛牛没有图中那么奇怪的容器，他只有 $n$ 支规格相同的试管，这些试管中有一些底部是相互连通的，为了避免混淆试管之间的连通性，牛牛给第 $i$ 支试管标记为 $tab_i$ ——若两支试管标记相同，则它们连通。初始时，每支试管中都没有水，且试管体积视为无穷大。现有三种操作：

• 加水：向第 $a$ 支试管中注入 $b$ 毫升水；

• 抽水：从第 $a$ 支试管中当前有多少毫升水。

• 查询：查询第 $a$ 支试管中当前有多少毫升水。

根据连通器原理，每个连通组内部的水会平分到各支试管中 ，因此,在同一连通组内，每支试管的水量始终相等。

输入描述

第一行输入两个整数 $n,m(1≦n,m≦10^5)$ ,新试管数量、操作数量。

第二行输入 $n$ 个整数，$tab_1,tab_2,...,tab_n(1≦tab_i≦n)$ 表示每支试管的连通标记。

此后 $m$ 行，每行先输入一个整数 $o(1≦o≦3)$ 。表示操作类型，对应三种操作，随后在同一行：

• 若 $o= 1$ ， 输入两个整数 $a,b(1≦a≦n;1≦b≦10^4)$ ,表示注水操作；

• 若 $o = 2$ ，输入两个整数 $a,b(1≦a≦n;1≦b≦10^4)$ ，表示抽水操作；保证此时该连通组至少有 $b$ 毫升水可抽；

• 若 $o=3$ ，输入一个整数 $a(1≦a≦n)$，表示查询操作。

除此之外，保证至少存在一次查询操作。

输出描述

对于每个查询操作，新起一行输出一个实数，表示第 $a$ 支试管中水的体积。

由于实数的计算存在误差，当误差的量级不超过 $10^{-5}$ 时，您的答案都将被接受。具体来说，设您的答案为 $a$ ，标准答案为 $b$ ，当且仅当 $\frac{∣a-b∣}{max(1,∣b∣)}≤10^{-5}$ 时，您的答案将被接受。

样例1

输入

5 6
1 2 1 2 3
1 1 5
3 1
1 2 7
3 4
2 4 4
3 2

输出

2.500000
3.500000
1.500000

说明

在这个样例中，第 $1$ 支试管和第 $3$ 支试管连通，第 $2$ 支试管和第 $4$ 支试管连通。操作如下:

• 注水:向第 $1$ 支试管中注入 $5$ 毫升水，此时第 $1,3$ 支试管中各有 $2.5$ 毫升水;

• 注水:向第 $2$ 支试管中注入 $7$ 毫升水，此时第 $2,4$ 支试管中各有 $3.5$ 毫升水；

• 抽水 : 从第 $4$ 支试管中抽出 $4$ 升水，此时第 $2,4$ 支试管中各有 $1.5$ 毫升水。需要注意的是，虽然直观地看第 $4$ 支试管中此时只有 $3.5$ 毫升水，但是第 $4$ 支试管所在的整个连通器中有 $7$ 毫升水，因此牛牛是可以抽取 $4$ 升水的。

样例2

输入

6 8
1 2 2 2 3 1
1 3 10
3 2
2 3 2
3 3
1 1 9
1 5 10
3 5
3 6

输出

3.333333
2.6666667
10.000000
4.500000