P3380 【Template】Tree of Trees

You need to implement a data structure (you may refer to the problem title) to maintain a sequence, supporting the following operations: 1. Query the rank of $k$ within a range. 2. Query the value whose rank is $k$ within a range. 3. Modify the value at a certain position. 4. Query the predecessor of $k$ within a range (the predecessor is defined as the largest number that is strictly less than $k$, and if it does not exist, output **`-2147483647`**). 5. Query the successor of $k$ within a range (the successor is defined as the smallest number that is strictly greater than $k$, and if it does not exist, output **`2147483647`**). For a set of elements, the rank of a number is defined as the count of elements strictly smaller than it plus one, and the number with rank $k$ is defined as “the element that would be at position $k$ after sorting the elements in ascending order.”

The first line contains two integers $n, m$, denoting a sequence of length $n$ and $m$ operations. The second line contains $n$ integers, representing the sequence. The next $m$ lines each contain an operation, where $opt$ denotes the operation id. If $opt=1$, it is operation 1. Then there are three integers $l~r~k$, meaning: query the rank of $k$ in the range $[l,r]$. If $opt=2$, it is operation 2. Then there are three integers $l~r~k$, meaning: query the number whose rank is $k$ in the range $[l,r]$. If $opt=3$, it is operation 3. Then there are two integers $pos~k$, meaning: modify the value at position $pos$ to $k$. If $opt=4$, it is operation 4. Then there are three integers $l~r~k$, meaning: query the predecessor of $k$ in the range $[l,r]$. If $opt=5$, it is operation 5. Then there are three integers $l~r~k$, meaning: query the successor of $k$ in the range $[l,r]$.

For operations $1, 2, 4, 5$, output one line for each query, representing the result.

Constraints: $1\le n,m\le 5\times 10^4$, and the values in the sequence are always in $[0, 10^8]$ at any time. Problem source: bzoj3196 / Tyvj1730, with thanks. This testdata is original to Luogu. Special reminder: this testdata does not guarantee that the answers for operations 4 and 5 always exist, so please be sure to handle the nonexistence cases. Translated by ChatGPT 5