platinum_Splitting_Haybales (USACO US_Open_Contest)
Time limit: 2 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: data structures, segment tree, function composition, piecewise functions

Farmer John wants to fairly split haybales between his two favorite cows Bessie
and Elsie. He has $N$ ( $1\le N\le 2\cdot 10^5$) haybales sorted in
non-increasing order,  where the $i$-th haybale has $a_i$ units of hay
($2\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
$a_l, \dots, a_r$ between Bessie and Elsie. He has decided to process the
haybales in order from $l$ to $r$, and when processing the $i$-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 $Q$ ($1\le Q\le 2\cdot 10^5$) queries, each with three integers
$l,r,x$ ($1\le l\le r\le N$, $|x|\le 10^9$). For each query, output how many
more units of hay Bessie will have than Elsie after processing haybales $l$ to
$r$, if Bessie starts with $x$ more units than Elsie. Note that this value is
negative if Elsie ends up with more haybales than Bessie.
INPUT FORMAT (input arrives from the terminal / stdin):
First line contains $N$.
Second line contains $a_1\dots a_N$.
Third line contains $Q$.
Next $Q$ lines contain $l, r, x$.
OUTPUT FORMAT (print output to the terminal / stdout):
Output $Q$ lines, containing the answer for each query.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
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.
SAMPLE INPUT:
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
SAMPLE OUTPUT:
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.
SCORING:
Input 3: $Q\le 100$
Inputs 4-6: At most $100$ distinct $a_i$
Inputs 7-22: No additional constraints.
Problem credits: Benjamin Qi

Starter code:

Grader code:

Setup script:

Evaluation script: