题目详情题解（0）讨论（0）提交记录（0）

A90529.「USACO 2024 US Open Platinum」Splitting Haybales

省选/NOI-

通过率：0%

时间限制：2.00s

内存限制：256MB

题目描述

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

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

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

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

输入格式

第一行一个整数 NN。

第二行 NN 个整数 a1,…,aNa_1,\ldots,a_N。

第三行一个整数 QQ。

接下来 QQ 行每行三个整数 l,r,xl,r,x。

输出格式

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

输入输出样例

  • 输入#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≤100Q\le 100
  • 测试点 4-6：最多有 100100 个不同的 aia_i
  • 测试点 7-22：无附加限制

供题：Benjamin Qi

首页