06743. USACO·干草堆分拆 未做

Farmer John 想要将干草堆公平地分配给他最喜欢的两头奶牛 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 \cdots \ge a_N\ge 1$）。

Farmer John 正在考虑将一个连续区间的干草堆 $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$ 行，包含每个询问的答案。

【样例解释】

对于第 5 个询问，有 $5$ 个干草堆需要处理。Bessie 收到 $4$ 单位干草，然后 Elsie 收到 $4$ 单位干草，然后 Bessie 收到 $3$ 单位干草，然后 Elsie 收到 $1$ 单位干草，然后 Elsie 收到 $1$ 单位干草。

• 测试点 4-6：至多存在 $100$ 个不同的 $a_i$。

• 测试点 7-22：没有额外限制。

【数据规模与约定】

• 测试点 3：$Q\le 100$。

• 测试点 4-6：至多存在 $100$ 个不同的 $a_i$。

• 测试点 7-22：没有额外限制。

供题：Benjamin Qi