Description

Given a sequence of $n$ numbers $a_1,a_2 \dots a_n$, you need to support two operations:

• Q l r k queries the $k$-th smallest number among indices in the interval $[l,r]$.
• C x y sets $a_x$ to $y$.

Input Format

The first line contains two positive integers $n,m$, the sequence length and the number of operations. The second line contains $n$ integers, representing $a_1,a_2 \dots a_n$. The next $m$ lines each describe an operation, which is one of the two types above.

Output Format

For each query, output one integer on a separate line representing the answer.

5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

3
6

Hint

Constraints:

• For $10\%$ of the testdata, $1 \le n,m \le 100$.
• For $20\%$ of the testdata, $1 \le n,m \le 1000$.
• For $50\%$ of the testdata, $1 \le n,m \le 10^4$.
• For $100\%$ of the testdata, $1 \le n,m \le 10^5$, $1 \le l \le r \le n$, $1 \le k \le r-l+1$, $1 \le x \le n$, $0 \le a_i,y \le 10^9$.

Pay attention to constant-factor optimizations, but straightforward implementations of overall binary search on values ("整体二分") and tree-of-trees ("树套树") can both pass in about 1000 ms per test point.

Source: bzoj1901.

This problem uses custom Luogu testdata, generated with CYaRon in $5$ minutes.

Translated by ChatGPT 5