{"problem":{"name":"[USACO24OPEN] Splitting Haybales P","description":{"content":"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 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10284"},"statements":[{"statement_type":"Markdown","content":"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$).  \n\nFarmer 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).  \n\nYou 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.\n\n## Input\n\nFirst line contains $N$.  \n\nSecond line contains $a_1\\dots a_N$.  \n\nThird line contains $Q$.  \n\nNext $Q$ lines contain $l, r, x$.\n\n## Output\n\nOutput $Q$ lines, containing the answer for each query.\n\n[samples]\n\n## Note\n\n##### For Sample 1:\nFor 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.   \n\nFor 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.  \n\nFor 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. \n##### For Sample 2:\nIn 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.  \n\n#### SCORING:\n- Input 3: $Q\\le 100$.\n- Inputs 4-6: At most $100$ distinct $a_i$.\n- Inputs 7-22: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10284","tags":["USACO","平衡树","2024","均摊分析"],"sample_group":[["2\n3 1\n15\n1 1 -2\n1 1 -1\n1 1 0\n1 1 1\n1 1 2\n1 2 -2\n1 2 -1\n1 2 0\n1 2 1\n1 2 2\n2 2 -2\n2 2 -1\n2 2 0\n2 2 1\n2 2 2","1\n2\n3\n-2\n-1\n0\n1\n2\n-1\n0\n-1\n0\n1\n0\n1"],["5\n4 4 3 1 1\n7\n1 1 20\n1 2 20\n1 5 20\n1 1 0\n1 5 0\n1 4 0\n3 5 2","16\n12\n7\n4\n1\n2\n1"]],"created_at":"2026-03-03 11:09:25"}}