#1291. 【模板】线段树分裂

【模板】线段树分裂

题目描述

给出一个可重集 aa(编号为 11),它支持以下操作:

0 p x y:将可重集 pp 中大于等于 xx 且小于等于 yy 的值移动到一个新的可重集中(新可重集编号为从 22 开始的正整数,是上一次产生的新可重集的编号+1)。

1 p t:将可重集 tt 中的数放入可重集 pp,且清空可重集 tt(数据保证在此后的操作中不会出现可重集 tt)。

2 p x q:在 pp 这个可重集中加入 xx 个数字 qq。

3 p x y:查询可重集 pp 中大于等于 xx 且小于等于 yy 的值的个数。

4 p k:查询在 pp 这个可重集中第 kk 小的数,不存在时输出 -1。

输入格式

第一行两个整数 n,mn,m,表示可重集中的数在 1∼n1\sim n 的范围内,有 mm 个操作。

接下来一行 nn 个整数,表示 1∼n1 \sim n 这些数在 aa 中出现的次数 (ai≤m)(a_{i} \leq m)。

接下来的 mm 行每行若干个整数,第一个数为操作的编号 optopt(0≤opt≤40 \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

题目来源:洛谷 P5494