A6721 | 「NOI2022」冒泡排序

本题共 $25$ 个测试点。全部测试点满足：$1 \leq T \leq 1000$，$1 \leq \sum n, \sum m \leq 10^6$，$1 \leq L_i \leq R_i \leq n$，$0 \leq V_i \leq 10^9$。

其中 $\sum n, \sum m$ 分别表示所有测试点的 $n$ 的总和和 $m$ 的总和。$\sum n^2, \sum m^2, \sum n^3, \sum m^3$ 的含义类似。

| 测试点 | 数据范围 | 特殊性质 |
|:------------:|:------------------------------------------------------:|:------------:|
| $1 \sim 4$ | $n,m \leq 7$，且最多 $2$ 组数据不满足 $n, m \leq 5$ | |
| $5 \sim 7$ | $n,m \leq 17$，且最多 $3$ 组数据不满足 $n, m \leq 9$ | A |
| $8 \sim 10$ | $n,m \leq 100$，$\sum n^3,\sum m^3 \leq 4 \times 10^7$ | A |
| $11 \sim 12$ | $n,m \leq 2000$，$\sum n^2,\sum m^2 \leq 4 \times 10^7$ | A |
| $13 \sim 14$ | $n,m \leq 2000$，$\sum n^2,\sum m^2 \leq 4 \times 10^7$ | B |
| $15 \sim 16$ | $n,m \leq 2000$，$\sum n^2,\sum m^2 \leq 4 \times 10^7$ | C |
| $17 \sim 18$ | $n,m \leq 2000$，$\sum n^2,\sum m^2 \leq 4 \times 10^7$ | |
| $19$ | $\sum n,\sum m \leq 10^6$ | A |
| $20$ | $\sum n,\sum m \leq 10^6$ | B |
| $21 \sim 22$ | $\sum n,\sum m \leq 10^6$ | C |
| $23 \sim 25$ | $\sum n,\sum m \leq 10^6$ | |

特殊性质 A：对于 $1 \leq i \leq m$，$0 \leq V_i \leq 1$。
特殊性质 B：对于 $1 \leq i \leq m$，$L_i = R_i$。
特殊性质 C：输入给出的 $m$ 个区间 $[L_i, R_i]$ 两两不相交。

本题的部分测试点输入量较大。我们建议你使用较为快速的读入方式。