P3332 [ZJOI2013] K-th Largest Number Query

You need to maintain $n$ multisets of integers, numbered from $1$ to $n$. All sets are initially empty. There are $m$ operations: - `1 l r c`: Add $c$ to every set with index in $[l,r]$. - `2 l r c`: Query the $c$-th largest number in the union of all sets with indices in $[l,r]$. Note that the union of multisets does not remove duplicates, e.g., $\{1,1,4\}\cup\{5,1,4\}=\{1,1,4,5,1,4\}$.

The first line contains two positive integers $n, m$, the number of sets and the number of operations. Each of the next $m$ lines contains four integers describing one operation.

For each operation of type `2`, output one line with a single integer, the answer.

[Sample Explanation] The 1st operation adds one $1$ to sets $1$ and $2$. The 2nd operation adds one $2$ to sets $1$ and $2$. The 3rd operation queries the 2nd largest number in set $1$, which is $1$. The 4th operation queries the 1st largest number in set $1$, which is $2$. The 5th operation queries the 3rd largest number in the union $\{1,2,1,2\}$ of sets $1$ and $2$, which is $1$. Constraints $1 \le n,m \le 5\times 10^4$ $1 \le l,r \le n$ In operation `1`, $|c| \le n$ In operation `2`, $1 \le c < 2^{63}$, and the $c$-th largest number exists. --- $\text{upd 2023.8.23}$：Added a new set of hack testdata. Translated by ChatGPT 5