Description

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.”

Input Format

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]$.

Output Format

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

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

2
4
3
4
9

Hint

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