Editorial for HHPC1 P2 - Yuniformity Challenge

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: AustinJiang

To make all numbers in the subarray the same in at most two steps, let's break down all situations:

Situation 1 (achieved in zero steps):

All numbers within the subarray are originally the same.

This can be checked using the Prefix Sum Array (PSA) by summing the absolute differences between each pair of adjacent numbers.

Situation 2 (achieved in one step):

Apply the second strategy to multiply all numbers within the subarray by $0$ ~0~. This implies that a $0$ ~0~ is inside the subarray.

This can also be achieved using the PSA by counting the number of $0$ ~0~s in a prefix array.

Situation 3 (achieved in two steps):

If there is no zero, we can apply the first operation to add $x$ ~x~ to all numbers within the array to create a zero in the first step, reducing the situation to the second situation, which requires another step. To create a zero at a position by adding $x$ ~x~, the number at that position must originally be its opposite, which is $-x$ ~-x~.

Implementing this might be more complicated, but it can also be done using the PSA. Iterate through all $i$ ~i~ from $1$ ~1~ to $N$ ~N~. Use an array to record the last position each number has appeared. For each $i$ ~i~, let $pre[i]$ ~pre[i]~ be the last position where $-a[i]$ ~-a[i]~ has appeared. For each query, check whether the maximum value in the prefix from $pre[1]$ ~pre[1]~ to $pre[r]$ ~pre[r]~ is greater than or equal to $l$ ~l~.

The intended time complexity is $\mathcal{O}(N+Q)$ ~\mathcal{O}(N+Q)~.

Comments

0

volcano commented on Feb. 19, 2024, 1:38 a.m. ← edited →

For each query, check whether the maximum value in the prefix from $pre[1]$ ~pre[1]~ to $pre[l]$ ~pre[l]~ is greater than or equal to $r$ ~r~.

I believe it should say you have to check whether the maximum value in the prefix from $pre[1]$ ~pre[1]~ to $pre[r]$ ~pre[r]~ is greater than or equal to $l$ ~l~.