1000ms

Difficulty: 4

所属公司 : 科大讯飞

时间 :2025年9月6日

算法与标签>并查集

会员或题库专享

请先，开通会员或购买题库科大讯飞机考编程题库，可解锁完整内容。

购买科大讯飞机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（科大讯飞机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

每个连通标记对应一个静态连通组。维护两组信息：

$sz[g]$ ：标记为 $g$ 的油箱个数；
$sum[g]$ ：该组当前总油量。

三种操作转化为对哈希表的更新与查询：

题目内容

厂区有 $n$ 个规格相同、容积视为无穷的油箱。第 $i$ 个油箱的连通标记为 $g_i$ ：标记相同的油箱底部互通，油会在组内均分，因此同一组内每个油箱的油量始终相等。初始时全部为空。

共有 $m$ 次操作，操作类型为以下三种之一：

类型 1：向第 $a$ 个油箱注入 $b$ 毫升油；
类型 2：从第 $a$ 个油箱所在连通组抽出 $b$ 毫升油，保证该组当前总量至少为 $b$ 毫升；
类型 3：查询第 $a$ 个油箱当前有多少毫升油。

约束：油箱个数与操作次数均不超过 10^5，连通标记不超过油箱个数，注入或抽出的毫升数不超过 10^4。保证至少有一次查询。