Author: Kirito

Subtask 1

This subtask is intended to reward brute force solutions.

Subtask 2

This subtask is intended to reward ~O(N^2)~ solutions.

These sequences are related to an object in algebraic combinatorics called Raney sequences. In particular, the observations for this problem are precisely those used to give a combinatorial proof of the Lagrange Implicit Funtion Theorem.

(Raney Sequence)
A Raney sequence ~a_1,a_2,\ldots,a_k~ is a sequence where:

• ~a_i\geq -1~ for all ~1\leq i\leq k~;
• all proper prefix sums ~a_1 + \cdots + a_j~ (~\leq j < k~) are non-negative;
• ~a_1 + \cdots + a_k = -1~.

One possible solution is as follows: note that the ~R_i~ form a tree ~T~ with vertices ~\{1, \ldots, N\}~, rooted at 1. Now let ~v_1, v_2, \ldots, v_N~ be a BFS ordering of the vertices of ~T~, where ~v_1 = 1~. Then ~A_i~ is precisely the number of children nodes of ~v_i~ in ~T~.

~a_1,\ldots,a_k~ is a Raney sequence iff there exists a tree ~T~ rooted at 1 such that if ~v_1,\ldots,v_k~ is a BFS ordering of the vertices of ~T~ with ~v_1 = 1~, then ~a_i + 1~ is precisely the number of children of ~v_i~.

We will show one implication; the other implication is left as a (simple) exercise to the reader.

Let ~a_1,\ldots,a_k~ be a Raney sequence. We will construct the desired tree ~T~. Initially, let ~T~ consist of a single vertex with label 1. Let ~v(T)~ be the largest label of a vertex in ~T~, and let ~i = 1~.

1. Assign vertex ~i~ children with labels ~v(T) + 1, \ldots, v(T) + a_i + 2~;
2. Increment ~i~ by 1.
• If ~i < k~, return to step (1);
• Otherwise, terminate.

As ~a_i\geq -1~, it is clear that step (1) is always well-defined. Furthermore, at the ~i~th iteration, the number of vertices in the tree is exactly ~i + (a_1 + \cdots + a_i) + 1~; as ~(a_1 + \cdots + a_i)\geq 0~ for ~i < k~, and vertices are numbered consecutively, there exists a vertex with label ~i+1~ in our tree, so the next iteration is well-defined.

If ~i = k~, we get ~k + (a_1 + \cdots + a_k) + 1 = k~, and so our algorithm terminates, and ~T~ has exactly ~k~ vertices.

This leads to two possible ~O(N^2)~ solutions:

1. check if each cylic shift is a Raney sequence; or
2. for each cyclic shift, run the tree-building algorithm described above.

Subtask 3

By the previous lemma, the problem reduces to finding all cyclic shifts of an array that result in a Raney sequence.

Let ~a_1,\ldots,a_k~ be an array of integers where ~a_i\geq -1~ for all ~i~, and ~a_1 + \cdots + a_k = -1~. Then there exists a unique ~j~ such that ~a_{(i+j)}~ is a Raney sequence (where indices are taken mod ~k~ as necessary).

For ~1\leq i\leq k~, define ~s_i = a_1 + \cdots + a_i~. Let ~j~ be the smallest ~1\leq j\leq k~ that minimizes ~s_j~, i.e. ~j = \min\{i : s_i\leq s_{i'}\,\forall 1\leq i'\leq k\}~.

It is clear that ~a_{j+1} + \cdots + a_k + a_1 + \cdots + a_j = -1~, so it suffices to show all proper prefixes have non-negative sum. For ~i > j~, we have ~s_j\leq s_i~, hence $$\displaystyle a_{j+1} + \cdots + a_i = s_i - s_j\geq 0.$$

For ~i < j~, we have ~s_j\leq s_i - 1~, hence $$\displaystyle \begin{align*} a_{j+1} + \cdots + a_k + a_1 + \cdots + a_i &= (a_{j+1} + \cdots + a_k + a_1 + \cdots + a_j) - (a_{i+1} + \cdots + a_j) \\ &= -1 + (s_i - s_j)\geq 0. \end{align*}$$

We leave it as an exercise to the reader to show that all other indices ~j'\neq j~ do not yield valid Raney sequences. In particular, for ~j'\neq j~, one of the two previous inequalities will be violated, hence the corresponding prefix will have a strictly negative sum.

Thus there is a unique cyclic shift that results in a Raney sequence, and to compute ~j~, it suffices to find the minimum ~j~ that minimizes ~s_j~. This can be implemented in ~O(N)~ time.

Subtask 4

Implement the previous subtask with a segment tree that stores the leftmost index of the minimum prefix sum. In particular, the node corresponding to the interval ~[\ell, r]~ should store:

• ~\mathit{tot}_{\ell,r}~: the sum ~a_\ell + a_{\ell+1} + \cdots + a_r~;
• ~\mathit{prefix}_{\ell,r}~: the minimum prefix sum ~\min\{a_\ell, a_\ell + a_{\ell+1}, \ldots, a_\ell + \cdots + a_r\}~; and
• ~\mathit{idx}_{\ell,r}~: the smallest index that achieves the minimum prefix sum.

Then to merge the nodes ~[\ell,m]~ and ~[m+1,r]~, note that:

• ~\mathit{tot}_{\ell,r} = \mathit{tot}_{\ell,m} + \mathit{tot}_{m+1,r}~;
• ~\mathit{prefix}_{\ell,r} = \min\{\mathit{prefix}_{\ell,m}, \mathit{tot}_{\ell,m} + \mathit{prefix}_{m+1,r}\}~

and ~\mathit{idx}_{\ell,r}~ can be computed by comparing ~\mathit{prefix}_{\ell,r}~ to ~\mathit{prefix}_{\ell,m}~.

Thus each query can be answered by querying ~\mathit{idx}_{1,N}~, and each update implemented as two point update queries, giving an ~O(N + Q\log N)~ solution.