P5356 [Ynoi Easy Round 2017] Yuno Plays Poker


Yuno is not very good at playing poker. So she came up with a data structure problem. You are given a sequence $a$ of length $n$. You need to support $m$ operations of two types: 1. Query the $k$-th smallest value in the interval $[l, r]$. 2. Add $k$ to every element in the interval $[l, r]$.

One line with two integers $n, m$. The next line contains $n$ integers; the $i$-th integer represents $a_i$. The next $m$ lines each contain four integers $opt, l, r, k$, where $opt$ indicates which type of operation it is.

For each query, output one number as the answer. If there is no solution, output $-1$.

Idea: nzhtl1477. Solution: nzhtl1477 ($O(m\sqrt{n}(\Delta+\log n))$) solution, ccz181078 ($O(m\sqrt{n\log n})$) solution. Code: nzhtl1477 ($O(m\sqrt{n}(\Delta+\log n))$) code, ccz181078 ($O(m\sqrt{n\log n})$) code. Data: nzhtl1477. Constraints: $1\leq l\leq r \leq n\leq 10^5$, $1 \leq m \leq 10^5$, $-2\times 10^4\leq a_i, k\leq 2\times 10^4$, $opt \in \{1, 2\}$. --- $\text{upd 2022.8.18}$: A new set of hack testdata has been added. Translated by ChatGPT 5