P2617 Dynamic Rankings

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

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.

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

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](https://github.com/luogu-dev/cyaron) in $5$ minutes. Translated by ChatGPT 5