给出一个可重集 a(编号为 1),它支持以下操作:
0 p x y
:将可重集 p 中大于等于 x 且小于等于 y 的值移动到一个新的可重集中(新可重集编号为从 2 开始的正整数,是上一次产生的新可重集的编号+1)。
1 p t
:将可重集 t 中的数放入可重集 p,且清空可重集 t(数据保证在此后的操作中不会出现可重集 t)。
2 p x q
:在 p 这个可重集中加入 x 个数字 q。
3 p x y
:查询可重集 p 中大于等于 x 且小于等于 y 的值的个数。
4 p k
:查询在 p 这个可重集中第 k 小的数,不存在时输出 -1
。
第一行两个整数 n,m,表示可重集中的数在 1\sim n 的范围内,有 m 个操作。
接下来一行 n 个整数,表示 1 \sim n 这些数在 a 中出现的次数 (a_{i} \leq m)。
接下来的 m 行每行若干个整数,第一个数为操作的编号 opt(0 \leq opt \leq 4),以题目描述为准。
依次输出每个查询操作的答案。
5 12 0 0 0 0 0 2 1 1 1 2 1 1 2 2 1 1 3 3 1 1 3 4 1 2 2 1 1 4 2 1 1 5 0 1 2 4 2 2 1 4 3 2 2 4 1 1 2 4 1 3
3 2 4 3
对于 100\% 的数据,1 \le n \le 2 \times {10}^5,1 \le x, y, q \le m \le 2 \times {10}^5。保证数据合法。
模板