Summer Vacation

The obvious $O(n^2)$ suffix simulation is toast. The useful object for a suffix is not one answer, but the function describing what that suffix does to every possible starting balance.

1. Model one day as a function

Suppose the current balance is $x$ and today's value is $a$. After the day, the balance is

• $x+a$ when $x<a$;
• $x-a$ when $x\ge a$.

Call this transition $T_a(x)$.

Balances are much more tightly bounded than the sum of all $a_i$ suggests. Let $M=200000$, which is at least $2n$. For every $0\le x<M$:

• if $x<a$, then $x+a\le 2a-1\le 2n-1<M$;
• otherwise, $0\le x-a<M$.

Thus every $T_a$ maps the integer range $[0,M)$ back into itself. We can represent an entire suffix function using exactly $M$ values.

2. DP over suffix functions

Let $F_i(x)$ be the final balance after processing days $i,i+1,\ldots,n$, starting day $i$ with $x$ dollars. After the holidays there are no operations, so

$F_{n+1}(x)=x.$

Prepending day $i$ gives

$F_i(x)=F_{i+1}(T_{a_i}(x)).$

Suppose the array V currently stores $F_{i+1}(x)$ for every $x\in[0,M)$. Put $a=a_i$.

For $0\le x<a$, the first day changes $x$ into $x+a$. As $x$ runs through this range, the required old indices are

$a,a+1,\ldots,2a-1.$

For $a\le x<M$, the first day changes $x$ into $x-a$, producing old indices

$0,1,\ldots,M-a-1.$

Therefore the complete new function array is

$V_i=V_{i+1}[a,2a)+V_{i+1}[0,M-a),$

where $+$ means sequence concatenation.

This is not a rotation. The two source ranges can overlap, causing old elements to appear multiple times while other elements disappear. That small detail is where the problem hides the knife.

The answer for starting on day $i$ is simply $F_i(0)$, the first element of the new sequence.

3. Maintaining the sequence

We need a sequence of fixed length $M$ supporting:

• extracting a prefix or subarray;
• concatenating two extracted sequences;
• reading the first element.

An implicit treap supplies split(root, k), which returns the first $k$ elements and everything after them, and merge(left, right), which concatenates two sequences.

For one value $a$, perform:

1. Split the old root after $a$ elements.
2. Split the resulting tail after another $a$ elements. Its first part is $V[a,2a)$.
3. Independently split the original old root after $M-a$ elements. Its first part is $V[0,M-a)$.
4. Merge the two required parts.

The word independently matters. The ranges can overlap, so both must be extracted from the same unchanged version. Consequently, split and merge are persistent: before changing a node's child, they clone that node. Untouched subtrees are shared.

The treap is randomized without storing explicit priorities. When merging trees $L$ and $R$, it chooses the root from $L$ with probability

$\frac{|L|}{|L|+|R|},$

and from $R$ otherwise, then recursively merges along the boundary. This keeps the expected height logarithmic.

4. Rebuilding

Path copying leaves obsolete nodes in the arena. Also, randomized trees can occasionally acquire an ugly shape—probability is not a legal defense against stack overflow.

After every $B=5000$ updates, the implementation:

1. traverses the current sequence in order;
2. clears the node arena;
3. builds a perfectly balanced tree containing the same sequence.

A rebuild costs $O(M)$ and does not change any logical value. There are at most $20$ rebuilds under the constraints.

5. Complete algorithm

1. Initialize the maintained sequence to $[0,1,2,\ldots,M-1]$, representing $F_{n+1}(x)=x$.
2. Iterate through the days from $n$ down to $1$.
3. Replace the sequence by V[a_i..2a_i) + V[0..M-a_i) using persistent splits and a merge.
4. Store the first sequence element as the answer for arrival on day $i$.
5. Print the stored answers for days $n,n-1,\ldots,1$, corresponding to suffix lengths $1,2,\ldots,n$.

Correctness proof

Lemma 1. Every balance relevant to the process belongs to $[0,M)$.

Proof. Initially the balance is $0$. For any $x\in[0,M)$ and $a\le n$, earning produces $x+a\le2a-1<M$, while spending produces $0\le x-a<M$. Therefore the range is preserved after every day. $\square$

Lemma 2. If V represents $F_{i+1}$, then V[a_i..2a_i) + V[0..M-a_i) represents $F_i$.

Proof. For $x<a_i$, day $i$ produces $x+a_i$, so the new values come from old indices $a_i$ through $2a_i-1$. For $x\ge a_i$, it produces $x-a_i$, so the new values come from old indices $0$ through $M-a_i-1$. Concatenating these ranges lists $F_i(x)$ for every $x=0,1,\ldots,M-1$ in order. $\square$

Lemma 3. One treap update constructs exactly the sequence from Lemma 2.

Proof. Persistent splits extract both required ranges from the unchanged old sequence. merge preserves the internal order of both operands and places the second after the first, hence constructs their exact concatenation. $\square$

Theorem. Every printed value is the required final balance.

Proof. Initially the sequence is the identity function $F_{n+1}$. Processing days backward, Lemmas 2 and 3 show inductively that after handling day $i$, the sequence represents $F_i$. Its first element is therefore $F_i(0)$, the final balance when Monocarp arrives on day $i$. Printing these values for $i=n,n-1,\ldots,1$ gives answers for suffix lengths $1,2,\ldots,n$. $\square$

Complexity

Let $B=5000$ and $M=200000$. Each normal update takes expected $O(\log M)$ time. A rebuild costs $O(M)$, so total expected time is

$O\left(M+n\log M+\left\lfloor\frac nB\right\rfloor M\right).$

Under expected logarithmic height, the used arena between rebuilds contains $O(M+B\log M)$ nodes. The implementation pre-reserves a much larger arena to avoid expensive reallocations; the unusually generous memory limit is very much earning its paycheck here.