「USACO 2024 US Open Platinum」Splitting Haybales

题目描述

题目译自 USACO 2024 US Open Contest, Platinum Problem 2. Splitting Haybales

FJ 想把干草公平地分给他最喜欢的两头奶牛 Bessie 和 Elsie。他有 $N$ ($1\le N\le 2\cdot 10^5$) 捆按单调不增排列的干草，其中第 $i$ 捆干草有 $a_i$ ($2\cdot 10^5\ge a_1\ge a_2\ge \ldots \ge a_N\ge 1$) 单位的干草。

FJ 正在考虑把连续区间 $a_l,\ldots,a_r$ 中的干草分给 Bessie 和 Elsie。他决定按照从 $l$ 到 $r$ 的顺序处理草捆，在处理第 $i$ 捆干草时，他会把它分给目前草捆较少的奶牛（如果两头奶牛有同样数量的草捆，他会把这捆干草分给 Bessie）。

给你 $Q$ ($1\le Q\le 2\cdot 10^5$) 次询问，每次询问用三个整数 $l,r,x$ ($1\le l\le r\le N, |x|\le 10^9$) 表示。对于每次询问，输出如果开始时 Bessie 比 Elsie 多拥有 $x$ 个单位的干草，那么在处理完从 $l$ 到 $r$ 的干草后，Bessie 比 Elsie 多拥有多少单位的干草。注意，如果最终 Elsie 拥有的干草比 Bessie 多，那么这个值为负数。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $a_1,\ldots,a_N$。

第三行一个整数 $Q$。

接下来 $Q$ 行每行三个整数 $l,r,x$。

输出格式

输出 $Q$ 行，代表每次查询的答案。

样例 1

输入

2
3 1
15
1 1 -2
1 1 -1
1 1 0
1 1 1
1 1 2
1 2 -2
1 2 -1
1 2 0
1 2 1
1 2 2
2 2 -2
2 2 -1
2 2 0
2 2 1
2 2 2

输出

1
2
3
-2
-1
0
1
2
-1
0
-1
0
1
0
1

说明

• 对于第一次询问，Elsie 开始时比 Bessie 多 2 单位干草。在处理完第 1 捆干草后，Bessie 将得到 3 单位干草，这样 Bessie 将比 Elsie 多 1 单位干草。
• 对于第三次询问，Elsie 和 Bessie 开始时的干草数量相同。处理完第 1 捆干草后，Bessie 将得到 3 单位干草，Bessie 的拥有的干草比 Elsie 多 3 个单位。
• 对于第九次询问，Bessie 开始时比 Elsie 多 1 单位干草，处理完第 1 捆干草后，Bessie 比 Elsie 少 2 单位干草，处理完第 2 捆干草后，Bessie 比 Elsie 少 1 单位干草。

样例 2

输入

5
4 4 3 1 1
7
1 1 20
1 2 20
1 5 20
1 1 0
1 5 0
1 4 0
3 5 2

输出

16
12
7
4
1
2
1

说明
对于第五次询问，有 5 捆干草需要处理。Bessie 收到 4 单位干草，然后 Elsie 收到 4 单位干草，然后 Bessie 收到 3 单位干草，然后 Elsie 收到 1 单位干草，然后 Elsie 收到 1 单位干草。

数据范围与提示

• 测试点 3：$Q\le 100$
• 测试点 4-6：最多有 100 个不同的 $a_i$
• 测试点 7-22：无附加限制

供题：Benjamin Qi