#PU1429. USACO 2024 US Open Contest, Platinum — Problem 2. Splitting Haybales

    ID: 1667 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open24来源:usaco.orgscoring:equal_test_cases线段树差分

USACO 2024 US Open Contest, Platinum — Problem 2. Splitting Haybales

USACO 2024 US Open Contest, Platinum — Problem 2. Splitting Haybales

题目描述

Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has NN ( 1≤N≤2⋅1051\le N\le 2\cdot 10^5) haybales sorted in non-increasing order, where the ii-th haybale has aia_i units of hay (2⋅105≥a1≥a2≥⋯≥aN≥12\cdot 10^5\ge a_1\ge a_2 \ge \dots \ge a_N \ge 1). Farmer John is considering splitting a contiguous range of haybales al,…,ara_l, \dots, a_r between Bessie and Elsie. He has decided to process the haybales in order from ll to rr, and when processing the ii-th haybale he will give it to the cow who currently has less hay (if it is a tie, he will give it to Bessie). You are given QQ (1≤Q≤2⋅1051\le Q\le 2\cdot 10^5) queries, each with three integers l,r,xl,r,x (1≤l≤r≤N1\le l\le r\le N, ∣x∣≤109|x|\le 10^9). For each query, output how many more units of hay Bessie will have than Elsie after processing haybales ll to rr, if Bessie starts with xx more units than Elsie. Note that this value is negative if Elsie ends up with more haybales than Bessie.

输入格式

First line contains NN. Second line contains a1…aNa_1\dots a_N. Third line contains QQ. Next QQ lines contain l,r,xl, r, x.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 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
For the 1st query, Elsie starts with $2$ more hay than Bessie. Then, after
processing haybale $1$, Bessie will receive $3$ hay, and Bessie will have $1$
more hay than Elsie.
For the 3rd query, Elsie and Bessie start with the same number of hay. After
processing haybale $1$, Bessie will receive $3$ hay, and Bessie will have $3$
more hay than Elsie.
For the 9th query, Bessie starts with $1$ more hay than Elsie, then after
processing the 1st haybale, has $2$ less hay than Elsie, and after processing
the 2nd haybale, has $1$ less hay than Elsie.

样例 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
In the 5th query, there are $5$ haybales to process. Bessie receives $4$ hay, then Elsie
receives $4$ hay, then Bessie receives $3$ hay, then Elsie receives $1$ hay,
then Elsie receives $1$ hay.