Subtask 1

Brute force all possible ~3^N~ arrays and check if it satisfies all of the queries.

Time Complexity: ~O(NQ \times 3^N)~

Subtask 2

The intended solution is Gaussian elimination, where every query can be treated as a equation with ~N~ unknowns that sum up to ~z_i~. To simplify things, set the pivot at any index ~i~ to be the smallest subarray beginning at index ~i~. This allows for all entries in the matrix (other than the last column) to either be 1 or 0.

Time Complexity: ~O(N^2 \times Q)~

Subtask 3

A similar technique to Gaussian elimination will be used but with optimizations due to all equations being comprised of contiguous sequences of 1s. For every left index ~i~, have an ordered set storing the right index and sum of all subarrays that begin at index ~i~.

Iterate from left to right: if there is more than one subarray at any given index, take the subarray with the lowest right value and subtract it from all the other subarrays. For example, if we were at index ~2~ and had the following subarrays:

• [2, 4) = 6
• [2, 5) = 8
• [2, 6) = 4

We would end up with [4, 5) = 2 and [4, 6) = -2. Note that this process always creates new subarrays that begin at the exact same index - the right value of the smallest subarray.

Keep the [2, 4) subarray at index ~2~ and take the remaining subarrays and push them to index ~4~, as we now have two subarrays that begin at index ~4~ and end at indexes ~5~ and ~6~. Repeat this process and you should end up with subarrays (new queries) entirely consisting with a unique ~l~-value. This is called row echelon form.

Perform back-substitution:

• Initialize an array ans[]. Initially set everything to ~0~.
• Iterate from all indexes ~i~ from ~N~ to ~1~. Take the subarray beginning at ~i~, and let ~l~ be the left index of the subarray, ~r~ be the right index and ~v~ be the sum. Take the sum of all elements in ans[] from ~l+1~ to ~r~. Set ~ans[l]~ to ~v - sum~. Repeat.
• Print out all values in ans[].

Time Complexity: ~O(NQ)~ or ~O(NQ \times logN)~

Subtask 4

A similar idea to Subtask 3 will be used. Since all subarrays consist of a unique ~l~-value anyways, back-substitution can immediately be used.

For back substitution, a data structure of your choice can be used to optimize taking the sum of all elements from ~l+1~ to ~r~. Since all updates to ans will be done in decreasing order of index (as index ~l~ is the only update done, which we iterate from right to left), a suffix sum array will suffice.

Time Complexity: ~O(N + Q)~

Subtask 5

A similar idea to Subtask 3 will be used, but with a few key observations:

• Since we are simply storing the right index of all subarrays, subtracting the subarray with the smallest ~r~ at any given ~l~ from all other subarrays beginning at the same index is the same as removing a single element from the set at ~l~, and then taking the union of the set at ~l~ with the set at ~r~.
• The union of two sets can be done by taking the smaller set and inserting all its elements into the larger. Since when iterating from left to right, all "finished" sets will never be reused, this can be done in ~O(min(size(l), size(r)) \times logN)~. The sum of all union operations for all indexes will be at most ~O((N + Q) \times logN)~. Proof of this is left as an exercise to the reader.
• To handle subtracting the sum of the lowest right value subarray to all other subarrays, a lazy value for all indexes ~i~ representing a number to subtract from all subarrays beginning at ~i~ can be stored. When merging sets, resolve the lazy value of the smaller set (manually add lazy[i] to all elements in the smaller set, set lazy[i] to ~0~ afterwards)

Alternatively, realize that the Subtask 3 solution is only ~O(NQ)~ in its worst case; if instead of taking the subarray with the lowest right value, one takes a random subarray to subtract from other subarrays, the average case becomes amortized ~O((N + Q) \times logN)~. The proof of this is left as an exercise to the reader.

Time Complexity: ~O((N + Q) \times logN)~