P13509 [OOI 2024] Almost Certainly

Let's say that two multisets are equal $\textbf{almost certainly}$ if they are equal up to one element. That is, it should be possible to change at most one element in the first multiset so that they become equal. For example, the multisets $\{ 1, 1, 2 \}$ and $\{ 1, 2, 3\}$ are equal $\textit{almost certainly}$, $\{1, 1, 1 \}$ and $\{ 1, 1, 1 \}$ are equal $\textit{almost certainly}$, and $\{ 1, 2, 3 \}$ and $\{ 3, 4, 5 \}$ are not equal $\textit{almost certainly}$. A boy named Vasya really liked this definition and immediately came up with a problem about it. Vasya has two arrays $a$ and $b$, where $a_i \ge b_i$ for all $i$ from $1$ to $n$. Vasya can apply the following operation to array $a$ as many times as he wants (possibly zero times): choose any index $i$ ($1 \le i \le n$) and subtract 1 from $a_i$. At the same time, Vasya does not change array $b$. Vasya quickly understood what sequence of operations is needed to make the multiset of values of arrays $a$ and $b$ equal $\textit{almost certainly}$. Therefore, Vasya made the task more complicated --- now for each prefix of these arrays, he wants to know the minimum number of operations needed to make the prefixes of the arrays equal $\textit{almost certainly}$. More formally, for each $k$ from $1$ to $n$, Vasya wants to take the elements $a_1, a_2, \ldots, a_k$, as well as the elements $b_1, b_2, \ldots, b_k$. Vasya wants to know the minimum number of operations needed to make the multisets of these elements equal $\textit{almost certainly}$. Note that the task for each $k$ is solved $\textbf{independently}$.

Each test consists of one or more sets of input data. The first line contains a single integer $t$ ($1 \le t \le 100\,000$) --- the number of sets of input data. Then follows the description of the sets of input data. The first line of each set of input data contains a single integer $n$ ($1 \le n \le 200\,000$) --- the size of arrays $a$ and $b$. The second line of each set of input data contains $n$ integers $a_1,\ a_2,\ \ldots,\ a_n$ ($1 \le a_i \le 10^9$) --- the elements of array $a$. The third line of each set of input data contains $n$ integers $b_1,\ b_2,\ \ldots,\ b_n$ ($1 \le b_i \le a_i$) --- the elements of array $b$. Let $N$ be the sum of $n$ for all sets of input data in one test. It is guaranteed that $N \le 200\,000$.

For each set of input data, output $n$ integers, each of which is the answer to the task for each possible prefix length. It can be shown that the answer always exists.

### Note Consider the first set of input data in the first example. - For a prefix of length $1$, nothing needs to be done. - For a prefix of length $2$, $a_1 = 3$ needs to be decreased by 1 once, after which $a$ will be equal to $[2, 4]$, $b$ will be equal to $[1, 2]$, and they will be equal $\textit{almost certainly}$. Consider the third set of input data in the first example. - For a prefix of length $1$, nothing needs to be done. - For a prefix of length $2$, $a_2 = 17$ needs to be decreased by 4 times, after which the prefix of $a$ will be equal to $[11, 13]$, the prefix of $b$ will be equal to $[1, 13]$, and they will be equal $\textit{almost certainly}$. - For a prefix of length $3$, $a_1 = 11$ needs to be decreased by 1 and $a_3 = 14$ needs to be decreased by 1, after which $a$ will be equal to $[10, 17, 13]$, $b$ will be equal to $[1, 13, 11]$, and they will be equal $\textit{almost certainly}$. ### Scoring The tests for this problem consist of six groups. Points for each group are given only if all tests of the group and all tests of the required groups are passed. Please note that passing the example tests is not required for some groups. $\textbf{Offline-evaluation}$ means that the results of testing your solution on this group will only be available after the end of the competition. | Group | Points | Additional constraints | Required groups | Comment | |:-----:|:------:|:----------------------:|:---------------:|:-------:| | 0 | 0 | -- | -- | Examples. | | 1 | 16 | $N \leqslant 100$ | 0 | -- | | 2 | 13 | $N \leqslant 500$ | 0, 1 | -- | | 3 | 24 | $N \leqslant 3000$ | 0--2 | -- | | 4 | 13 | -- | -- | $a_i < b_{i + 1}$ | | 5 | 14 | -- | 4 | $a_i \leqslant a_{i + 1}, b_i \leqslant b_{i + 1}$ | | 6 | 20 | -- | 0--5 | **Offline-evaluation.** |