题目描述

有 $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$ 的问题。

输出格式

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

3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 10

0
0
0
1
1
2
2
3
3
4
0
0
0
0
1
1
1
2
2
2
0
0
0
0
1
1
1
2
2
2

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

0
0
0
0
2
2
2
2
4
4

3
1 1 1
1
1 1 1000000000000000000

499999999999999999

提示

样例 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 完成