P15574 [USACO26FEB] Milk Buckets S

有 $N$（$1\le N\le 2\cdot 10^5$）个桶堆叠在一起，从上往下数第 $i$ 个桶的容量为 $a_i$ 加仑（$1\le a_i\le 10^9$）。最上方桶的上面有一个水龙头，每秒向第一个桶中注入 $1$ 加仑牛奶。桶 $N$ 的下方有一个池子。 当一个桶在 $t$ 秒后达到其容量时，它会在第 $t+1$ 秒开始时翻转，将其内容物倒入下方的桶（如果不是最后一个桶）或池子（如果是最后一个桶）（并在第 $t+1$ 秒结束时恢复为接收状态）。桶在翻转期间无法收集牛奶；在这一秒内从上方桶流来的任何牛奶都会损失。此外，任何超过下方桶容量的部分也会损失。 处理 $Q$（$1\le Q\le 3\cdot 10^5$）个查询，每个查询由三个整数 $i$、$v$ 和 $t$ 指定： - 首先，设置 $a_i = v$（$1\le i\le N$，$1\le v\le 10^9$）。 - 然后回答以下问题：假设在时间 $0$ 时，所有桶和池子都是空的。确定在 $t$ 秒后池子中的牛奶加仑数（$1\le t\le 10^{18}$）。 这些 $a_i = v$ 的更新会持续影响后续查询。

第一行包含 $N$。 第二行包含 $a_1 \dots a_N$。 下一行包含 $Q$。 然后接下来的 $Q$ 行每行包含三个整数 $i$、$v$ 和 $t$。这意味着你应该先设置 $a_i = v$，然后回答针对 $t$ 的问题。

对每个问题，输出一行答案。

#### 样例 1 解释 当 $a=[1, 1, 1]$ 时， - 桶 $1$ 在时刻 $2,4,6,\dots$ 翻转 - 桶 $2$ 在时刻 $3,5,7,\dots$ 翻转 - 桶 $3$ 在时刻 $4,6,8,\dots$ 翻转 当 $a=[2, 1, 1]$ 时， - 桶 $1$ 在时刻 $3,6,9,\dots$ 翻转 - 桶 $2$ 在时刻 $4,7,10,\dots$ 翻转 - 桶 $3$ 在时刻 $5,8,11,\dots$ 翻转 当 $a=[2, 2, 1]$ 时， - 桶 $1$ 在时刻 $3,6,9,\dots$ 翻转 - 桶 $2$ 在时刻 $4,7,10,\dots$ 翻转 - 桶 $3$ 在时刻 $5,8,11,\dots$ 翻转 ### 评分标准 - 输入 4-5：$N \le 10$，$Q\le 100$，且所有 $t\le 10^4$ - 输入 6-11：$N\le 10^3$，$Q\le 10^4$ - 输入 12-23：无额外限制。 题目来源：Akshaj Arora 翻译由 DeepSeek 完成