QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: pystraf

Posted at: 2026-04-02 13:13:37

Last updated: 2026-04-02 13:13:59

Back to Problem

Editorial for #17181

A one-sided recursive segment tree can efficiently maintain information related to prefix/suffix maximums and minimums.

Obviously, operation $1$ affects the positions of the prefix maximum.

Build a segment tree where each node maintains the maximum value $m$ of $H$, the count $c$ of prefix maximum positions, and the sum $s$ of $S$.

Consider pushup. $c_{\text{ls}}$ can be used directly, but for $\text{rs}$ we need to satisfy the condition that its value is $\ge x = m_{\text{ls}}$. We need to recurse down. Suppose we are at node $u$. If $m_{\text{ls}} \le x$, recurse into $\text{rs}$; otherwise, recurse into $\text{ls}$ and add the part of $\text{rs}$ with values $\ge m_{\text{ls}}$, which is $c_u - c_{\text{ls}}$.

For operation $1$, we maintain a lazy tag $\text{t}$. When applying the tag, update positions in $u$ where the value is $\ge m_{\text{ls}}$. When pushing down, propagate to $\text{rs}$. This cannot be applied directly in a simple manner; we need to recurse similarly to the method above. When performing operation $1$, maintain the current prefix maximum $x$ and recurse into the $O(\log n)$ intervals obtained from splitting.

For operation $3$, we maintain another tag $h$, which is also propagated during recursion, without affecting the complexity.

Clearly, each recursion is $O(\log n)$, so the total complexity is $O(n\log n + q\log^2 n)$.

Comments

No comments yet.