A6143. 「USACO 2024 US Open Platinum」Splitting Haybales
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2024 US Open Contest, Platinum](http://usaco.org/index.php?page=open24results) Problem 2. [Splitting Haybales](http://usaco.org/index.php?page=viewproblem2&cpid=1429)**
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 多，那么这个值为负数。
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$。
第二行 $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
1 2 3 -2 -1 0 1 2 -1 0 -1 0 1 0 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
输出 #2
16 12 7 4 1 2 1
说明/提示
- 测试点 3：$Q\le 100$
- 测试点 4-6：最多有 $100$ 个不同的 $a_i$
- 测试点 7-22：无附加限制
供题：Benjamin Qi
- 测试点 4-6：最多有 $100$ 个不同的 $a_i$
- 测试点 7-22：无附加限制
供题：Benjamin Qi