CF626G Raffles

Johnny 在一个有 $n$ 个抽奖活动的嘉年华上。第 $i$ 个抽奖活动的奖品价值为 $p_{i}$。每个参与者可以在任意抽奖活动中投放彩票（同一抽奖活动可投入多张彩票）。抽奖活动结束时，每个抽奖箱从所有彩票中随机抽出一张，彩票所有者获得相应奖品。单个人可以从不同抽奖中赢得多个奖品。 然而，地区规定禁止任何参与者在某一抽奖活动中持有超过半数的彩票，即不得比其他所有参与者所持的彩票总数还多。为避免这种情况（并可能赢得部分奖品），组织者在每个抽奖箱内预先放入了一张彩票，这张彩票绝不会被移走。 Johnny 购买了 $t$ 张彩票，正思考如何分配到不同的抽奖活动。目前，第 $i$ 个抽奖箱内共有 $l_{i}$ 张彩票。他观察其他参与者如何投放或更改彩票数，并希望在任意时刻（即每次更新后）知道自己最多可以获得多少收益。请你求出在 Johnny 以最优方式分配自己的彩票的情况下，他的最高可能期望收益。Johnny 可以在每次更新后任意重新分配全部的彩票，但总数不超过 $t$，且在任何抽奖活动中不能比其他所有人加起来更多。 #

第一行包含三个正整数 $n$、$t$ 和 $q$（$1 \leq n, t, q \leq 200\ 000$），分别表示抽奖活动数量、Johnny 拥有的彩票数、总的操作次数。 第二行包含 $n$ 个空格分隔的正整数 $p_{i}$（$1 \leq p_{i} \leq 1000$），表示第 $i$ 个奖品的价值。 第三行包含 $n$ 个空格分隔的正整数 $l_{i}$（$1 \leq l_{i} \leq 1000$），表示第 $i$ 个抽奖箱初始的彩票数量。 最后 $q$ 行，每行描述一次操作，每次操作由两个整数 $t_{k}$、$r_{k}$（$1 \leq t_{k} \leq 2$，$1 \leq r_{k} \leq n$）组成。类型为 $1$ 的操作表示某参与者在第 $r_{k}$ 个抽奖箱中加一张彩票；类型为 $2$ 表示某参与者在第 $r_{k}$ 个抽奖箱中移除一张彩票。 保证每次操作后，每个抽奖箱中至少都有 $1$ 张非 Johnny 的彩票。 #

输出 $q$ 行，每行一个实数，表示在第 $k$ 次操作后，Johnny 以最优方式分配彩票时的最大期望收益。你的答案如果绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。 即：记你的答案为 $a$，标准答案为 $b$，则若 $|a - b| \leq 10^{-6} \times \max(1, |b|)$，答案视为正确。 #

在第一个样例中，Johnny 只能分配一张彩票。奖品价值分别为 $4$ 和 $5$，初始抽奖箱彩票数分别为 $1$ 和 $2$。第一次操作后，每个抽奖箱内有 $2$ 张彩票，Johnny 把自己的彩票投入第二个抽奖，期望收益为 $5 / 3$。第二次操作使第二个箱子中有 $3$ 张彩票，因此 Johnny 把票投入第一个抽奖，期望收益为 $2$。最后一次操作后，Johnny 仍将彩票放入第一个箱子，期望收益为 $4/3$。 在第二个样例中，Johnny 拥有的彩票数超过最大允许投入总和。比如第一次操作后，每个抽奖箱分别有 $7$、$6$ 和 $6$ 张彩票，因此 Johnny 最多只能投入 $19$ 张票，分别在三个箱子里实现 $7,6,6$ 上限，从而期望收益分别是 $7/14 \times 5, 6/12 \times 6, 6/12 \times 7$。同样，注意在后两次操作后，为了不超出第三抽奖箱上限，Johnny 需要减少第三箱的彩票数。 由 ChatGPT 5 翻译