U449821 [SPN D-Struct 02] Stable
题目背景
题目描述
请维护一个整数序列 $a$，支持如下操作：
1. 插入 $h$ 个新数 $x$。
2. 删除 $h$ 个数 $x$。保证 $a$ 中至少有 $h$ 个 $x$。
3. 求出 $a$ 中第 $k$ 小数，重复的数按多个计。记 $n'$ 表示操作时 $a$ 的长度，保证 $1 \le k \le n'$。
4. 给定数 $l,r$，求出 $a$ 中有多少个数在 $[l,r]$ 之间。
输入格式
第一行两个正整数 $n, q$，代表序列初始长度和操作个数。
第二行 $n$ 个整数 $x$，代表输入序列的初始值。
接下来 $q$ 行，每行开始一个正整数 $opt$，保证 $1 \le opt \le 4$。
如果 $opt=1,2$，接下来两个正整数 $h,x$。
如果 $opt=3$，接下来一个正整数 $k$。
如果 $opt=4$，接下来两个正整数 $l,r$。
输出格式
对于每个 $3,4$ 操作，输出一行答案。
说明/提示
**样例解释**
下面展示了每次操作前序列 $a$ 的值（已升序排列）。
```cpp
0 1 1 1 2 2 4 4 4 5
0 1 1 1 2 2 4 5
0 1 1 1 2 2 4 5 6 6
0 1 1 1 2 2 4 5 6 6
0 1 1 1 2 2 4 5 6 6
0 2 2 4 5 6 6
0 2 2 4 5 6 6
```
**数据范围及约定**
**数据范围及约定**
| 测试点编号 | $n,q,x \le$ | 特殊性质 |
| :----------: | :----------: | :----------: |
| 1 | $10$ | |
| 2 | $10^3$ | |
| 3 | $10^5$ | A |
| 4 | $10^5$ | |
| 5 | $2\times 10^5$ | A |
| 6 | $2 \times 10^5$ | |
| 7 | $3\times 10^5$ | A |
| 8 | $3\times 10^5$ | |
| 9 | $5 \times 10^5$ | A |
| 10 | $5 \times 10^5$ | |
- 特殊性质 A：$opt \in \{1,2,3\}$。
对于 $100\%$ 的数据，$0 \le x \le 5 \times 10^5$，$1 \le n,q,l,r \le 5 \times 10^5$，$1 \le h \le 10^6$。