Problem Description

Given a sequence $a=(a_1,a_2,\cdots,a_n)$, there are $m$ operations of two types:

• 1 l r x: For each $i\in[l,r]$, set $a_i \gets a_i - x \times [a_i > x]$.
• 2 l r: Compute $\sum\limits_{i=l}^r a_i$, $\min\limits_{i=l}^r a_i$, $\max\limits_{i=l}^r a_i$.

Constraints

• $1\le n,m\le 5\times 10^5$
• $1\le a_i,x\le 10^9$
• $1\le l\le r\le n$
• Time limit: $6\text{s}$, Memory limit: $64\text{MB}$

Solution

First, consider a potential-energy segment tree:

Each node maintains the min and max of its interval. When performing $\operatorname{subtract}$:

• If $\max < x$, the operation has no effect; exit directly.
• If $\min > x$, all numbers are affected; apply a lazy tag subtracting $x$ to the current node.

However, this approach has incorrect complexity. For a sequence alternating between $1$ and $10^9$, each $\operatorname{subtract}(1,n,1)$ operation would degrade to $O(nm)$.

Block partitioning on the sequence also seems infeasible. Instead, we partition by value. Since $V$ can be as large as $10^9$, we use exponential (geometric) partitioning: divide the value range into blocks $[b^i, b^{i+1})$, where $b$ is the base. There are $\lceil \log_b V\rceil$ such blocks.

For each value block, maintain a segment tree as described above. Each number can decrease at most $b$ times before falling out of its current block's range. Since a number can fall out $O(\log_b V)$ times total, we can directly find and insert these dropped elements by brute force.

The time complexity is $O(nb\log n\log_b V)$, and the space complexity is $O(n \log_b V)$.

However, due to the large constant factor, setting $b=2$ is insufficient; a larger $b$ is needed.

The memory limit is tight, but online processing prevents block-by-block handling. Notice that the bottom layers of the segment tree waste a lot of space. Therefore, when the node's length is less than a threshold $L$, handle it with brute force.

The parameters $b$ and $L$ need to be tuned based on the specific implementation. The author uses $b=32$ and $L=32$.

Additional details to note:

• Do not store $l$ and $r$ in segment tree nodes to avoid memory issues.
• When inserting new elements, do not incorrectly apply lazy tags to them.
• The number of elements in an interval is no longer $r-l+1$; maintain a $\textit{cnt}$ field to track the element count.
• Since all segment trees at the bottom level share a single $a$ array, check whether an element is within the current block's range before operating on it.