【模板】线段树分裂

题目描述

给出一个可重集 $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$),以**题目描述**为准。

输出格式


依次输出每个查询操作的答案。

输入输出样例

输入样例 #1

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

输出样例 #1

3
2
4
3

说明

对于 $30\%$ 的数据,$1\leq n \leq {10}^3$,$1 \le m \le {10}^3$; 对于 $100\%$ 的数据,$1 \le n \le 2 \times {10}^5$,$1 \le x, y, q \le m \le 2 \times {10}^5$。保证数据合法。 不开 `long long` 见祖宗!! --- 题面 by @[Limit](https://www.luogu.com.cn/user/86625) std by @[Limit](https://www.luogu.com.cn/user/86625)(线段树分裂) 验题 by @[Froggy](https://www.luogu.com.cn/user/100285)(平衡树,不过合并的复杂度假掉了,倒数第二个测试点就是 hack 数据) 数据 by @[Froggy](https://www.luogu.com.cn/user/100285)