[NOI2022] 冒泡排序 - 题目 - Infinity Online Judge

题目背景

最近，小 Z 对冒泡排序产生了浓厚的兴趣。

下面是冒泡排序的伪代码：

输入: 一个长度为 n 的序列 a[1...n]
输出: a 从小到大排序后的结果
for i = 1 to n do:
    for j = 1 to n - 1 do
        if (a[j] > a[j + 1])
            交换 a[j] 与 a[j + 1] 的值

冒泡排序的交换次数被定义为在排序时进行交换的次数，也就是上面冒泡排序伪代码第六行的执行次数。他希望找到一个交换次数尽量少的序列。

题目描述

小 Z 所研究的序列均由非负整数构成。它的长度为 $n$ ，且必须满足 $m$ 个附加条件。其中第 $i$ 个条件为：下标在 $[L_i, R_i]$ 中的数，即 $a_{L_i}, a_{L_{i+1}},\dots,a_{R_i}$ 这些数，其最小值恰好为 $\boldsymbol{V_i}$ 。

他知道冒泡排序时常会超时。所以，他想要知道，在所有满足附加条件的序列中，进行冒泡排序的交换次数的最少值是多少。

输入格式

本题有多组数据。

输入的第一行包含一个正整数 $T$ 。

对于每组数据，第一行包含两个正整数 $n,m$ 。数据保证 $1 \leq n,m \leq 10^6$ 。

接下来 $m$ 行，每行三个非负整数 $L_i, R_i, V_i$ ，表示一组附加条件。数据保证 $1 \leq L_i \leq R_i \leq n$ 、 $0 \leq V_i \leq 10^9$ 。

输出格式

输出共 $T$ 行，每行一个整数。

对于每组数据，如果存在满足这 $m$ 个附加条件的序列，则输出在所有满足附加条件的序列中，冒泡排序交换次数的最小值。如果不存在满足所有条件的序列，则输出 $-1$ 。

样例 #1

样例输入 #1

样例输出 #1

提示

【样例解释 #1】

这组数据的约束条件为 $a_1 = 2022, \min\{a_2, a_3\} = 39$ 。

若 $a_2 = 39$ ，且 $39 \leq a_3 < 2022$ ，则冒泡排序只有第一轮有交换操作，这一轮交换了 $a_1, a_2$ 和 $a_2, a_3$ ，总交换次数为 $2$ 。

若 $a_2 = 39$ ，且 $a_3 \geq 2022$ ，则冒泡排序只有第一轮有交换操作，这一轮仅仅交换 $a_1, a_2$ ，总交换次数为 $1$ 。

若 $a_3 = 39$ ，且 $39 < a_2 < 2022$ ，则冒泡排序算法第一轮交换 $a_1, a_2$ 和 $a_2, a_3$ ，第二轮交换 $a_1, a_2$ 。总交换次数为 $3$ 。

若 $a_3 = 39$ ，且 $a_2 \geq 2022$ ，则冒泡排序算法第一轮交换 $a_2, a_3$ ，第二轮交换 $a_1, a_2$ 。总交换次数为 $2$ 。

因此，交换次数的最小值为 $1$ 。

【样例 #2】

见附件中的 bubble/bubble2.in 与 bubble/bubble2.ans。

【样例 #3】

见附件中的 bubble/bubble3.in 与 bubble/bubble3.ans。

这个样例满足测试点 $8 \sim 10$ 的条件。

【样例 #4】

见附件中的 bubble/bubble4.in 与 bubble/bubble4.ans。

这个样例满足测试点 $13 \sim 14$ 的条件。

【样例 #5】

见附件中的 bubble/bubble5.in 与 bubble/bubble5.ans。

这个样例满足测试点 $15 \sim 16$ 的条件。

【样例 #6】

见附件中的 bubble/bubble6.in 与 bubble/bubble6.ans。

这个样例满足测试点 $23 \sim 25$ 的条件。

附件下载地址

【数据范围】

本题共 $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]$ 两两不相交。

【提示】

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

Infinity Online Judge

InfOJ

#205. [NOI2022] 冒泡排序