Splitting Haybales

题目描述

农夫约翰想把干草捆公平地分给他最喜欢的两头牛 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 \dots \ge a_N \ge 1$）。 农夫约翰考虑将一段连续的干草捆 $a_l, \dots, 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$。 第二行包含 $a_1\dots a_N$。 第三行包含 $Q$。 接下来 $Q$ 行每行包含 $l, r, x$。

输出格式

输出 $Q$ 行，每行包含对应询问的答案。

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

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

提示

对于第 1 个询问，Elsie 一开始比 Bessie 多 $2$ 单位干草。之后处理第 $1$ 个干草捆时，Bessie 会获得 $3$ 单位干草，于是 Bessie 将比 Elsie 多 $1$ 单位干草。 对于第 3 个询问，Elsie 和 Bessie 一开始的干草数量相同。处理第 $1$ 个干草捆后，Bessie 会获得 $3$ 单位干草，于是 Bessie 将比 Elsie 多 $3$ 单位干草。 对于第 9 个询问，Bessie 一开始比 Elsie 多 $1$ 单位干草，然后在处理第 1 个干草捆后，比 Elsie 少 $2$ 单位干草；在处理第 2 个干草捆后，比 Elsie 少 $1$ 单位干草。 在第 5 个询问中，需要处理 $5$ 个干草捆。Bessie 获得 $4$ 单位干草，然后 Elsie 获得 $4$ 单位干草，然后 Bessie 获得 $3$ 单位干草，然后 Elsie 获得 $1$ 单位干草，然后 Elsie 获得 $1$ 单位干草。 SCORING: Input 3: $Q\le 100$ Inputs 4-6: 至多有 $100$ 个不同的 $a_i$ Inputs 7-22: 无额外限制。 题目致谢：Benjamin Qi

标签: USACO|2024|Platinum

来源

USACO|2024|Platinum