Observation: what is the property of Query 1?

While Query 2 and Query 3 can be processed with an ordinary lazily-evaluated segment tree (we call it lazyseg), Query 1 is problematic. Let us take a look at the property of this query.

1. It cannot be handled with an ordinary lazyseg.

The algebraic structure that can be handled with a lazyseg is in fact very limited. (The conditions are described in ACL (AC Library) reference). The integer division like Query 1 does not satisfy them, so it cannot be directly handled with a lazyseg.

2. Every application of query halves the value of a_i

Every time a Query 1 is invoked, each element in the segment is changed from \(a_i\) to \(\lfloor a_i / x\rfloor \leq a_i / 2\), so the value of the element is halved, or even less. Moreover, once it reaches \(0\), it is not affected by Query 1 until it is affected by Query \(2\) (updating query). This is the key to reducing the complexity.

With these points in mind, let’s consider the solution. Here, we introduce two ways.

Solution 1: manage segments with a set

The first solution is pretty orthodox: to manage the segments in a set, just as in the Ex problem in the last contest.
Consider managing “segments with the same value of at least \(1\)” with a std::set. Also, let us prepare a lazyseg that accepts a range assign and a range sum, which manages the elements of \(A\) too. Query 2 can be processed fast by inserting segments appropriately to the set::set and querying a range assign to the lazyseg. Query 3 can be answered using lazyseg. The initialization of the data structures by the given \(A\) can be regarded as \(N\) queries of Query \(2\), so it can be processed fast too.
The issue is Query 1. First, scan the std::set to enumerate the non-zero segments included in \([L,R]\). Since each segment has the same value, the value after integral division can be instantly found, and the values in the lazyseg can be updated in an \(\mathrm{O}(\log N)\) time each. Also, if the value reached \(0\), remove it from the std::set.

Now let us consider the complexity. A segment is inserted in the std::set at most \(\lceil \log \max(A) \rceil + 1\) times. A new segment is inserted at most \(N + \mathrm{O}(Q)\) times. Therefore, the total time complexity is \(\mathrm{O}( (N + Q) \log N \log \max(A))\).

Sample code

As an advanced topic, we will introduce another solution for those who have knowledge on or are interested in data structures: using Segment Tree Beats!.

Solution 2: Segment Tree Beats!

Segment Tree Beats! (we call it Beats) is a data structure developed by people engaged in Informatics Olympiad in China.

• Article in Codeforces: an editorial by the author Ji. In China, it is also called “吉老师线段树”.

Beats is an advanced version of lazyseg, so we will explain based on the implementation of lazy_segtree in ACL.

Given a range-update query on a lazyseg (as in apply function in ACL), the operator is applied as follows:

1. From root to leaves, propagate the values for lazy evaluation (as in push function in ACL).
2. For \(\mathrm{O}(\log N)\) number of segments, apply the operation in order to update the value for the lazy evaluation (as in all_apply function in ACL).
3. From leaves to root, update the values based on the values after the operations are applied (as in update function in ACL).

Such steps enable range update and range sum queries because the monoid \(S\) and the operator \(F\) has a certain good property.
Then, what if the operator “sometimes fails?” That is, consider the situation in which an operator sometimes can be, and sometimes can’t be, applied to the monoid based on its current value. (If the operator has such a property, trying to directly store them on a lazyseg and a segtree will result in a mess due to the failure in Step 2.)
For now, let us assume that it can always be applied to a segment of length \(1\). Then, we can construct an algorithm that works correctly by recursively repeating the operations of “if the application fails, try applying it to its children” (because no matter how many times it fails, it finally end up in a segment of length \(1\).) The algorithm looks like this:

1. From root to leaves, propagate the values for lazy evaluation.
2. For \(\mathrm{O}(\log N)\) number of segments, try to apply the operation.
   • If it succeeds, apply it in the same way as an ordinary lazyseg to update the values for lazy evaluations.
   • Otherwise, try to apply it to the children element. Repeat it recursively until it succeeds.
3. From leaves to root, update the values based on the values after the operations are applied.

While the algorithm above never fails, it costs \(\mathrm{O}(N)\) time at worst, so we have to cope with it.
Let us define ordinary nodes by the nodes visited by a lazyseg, and the extra nodes by the nodes visited by Beats for the first time. Ordinary nodes do not matter, since there are \(\mathrm{O}(\log N)\) of them, just as in lazyseg; the number of extra nodes matter. Here, if the number of extra nodes visited by the entire problem can be bounded by \(\mathrm{o}(QN)\) for the entire problem by appropriately designing monoids and operators, the update query can be processed in an amortized \(\mathrm{o}(N)\) time.

• While the idea itself is easy, using Beats is difficult as it requires a n ad-hoc design and analysis depending on problems.

The answer for this problem is as follows.

The element to store in Beats for ABC256H

For each segment \([L,R]\), store the following four elements:

• \(a_L\)
• \(\sum_{i=L}^R a_i\)
• The length of the segment (\(R - L + 1\))
• A flag indicating whether all values \(a_i\) in the segment are equal

The operator can be applied if and only if “the flag is true.” For more details, pleas refer to the Sample code.

Analysis

All the parts except for extra node can be processed in a total of \(\mathrm{O}(N + Q \log N)\) time, so we don’t need to consider them. We will evaluate the number of extra nodes to be visited.

For a segment \([l, r]\), let us define \(f(l,r)\) by:

\[ f(l, r) = \begin{cases} 0 & \text{if } a_l = a_{l+1} = \dots = a_r \\ -\log_2 \max(a_l, a_{l+1}, \dots, a_{r}) - 1 & \text{otherwise.} \end{cases} \]

Also, let us define the potential \(\phi\) by the sum of \(f\) over all nodes. Focusing on the transition of \(\phi\), we will show that extra nodes are visited at most \(2(N + Q \lceil \log N \rceil) \lceil \log \max(A) + 1 \rceil\) times.

Let \(\phi_i :=\) (the potential after the \(i\)-th query has been processed). We have \(\phi_0 \geq -2N \lceil \log \max(A) + 1 \rceil\). Also, the number of new nodes that becomes \(f(l, r) \neq 0\) by each execution of Query \(2\) is equal to the number of calls of update function in ACL, so when \(i\) is Query 2, \(\phi_i - \phi_{i-1} \geq -2 \lceil \log N \rceil \lceil \log \max(A) + 1 \rceil\). Therefore, the total delta of the potential over all queries is bounded by \(-2(N + Q \lceil \log N \rceil) \lceil \log \max(A) + 1 \rceil\).

Also, every time Query \(1\) visits one extra node, the maximum value of that nodes becomes less than \(1/2\) so the potential increases by at least \(1\). Also, by definition, the potential is always less than or equal to \(0\). Therefore, we have confirmed that the number of times that extra nodes are visited is at most \(2(N + Q \lceil \log N \rceil) \lceil \log \max(A) + 1 \rceil\).

Therefore, the total time complexity using Beats is \(\mathrm{O}( (N+Q \log N) \log \max(A))\).

If you can write lazyseg, implement Beatss should not be that difficult. Also, hitonanode introduces a way to tweak lazyseg in ACL to make it Beats, which may help you understanding. Article by hitonanode (Japanese))

Sample code