#P8500. [NOI2022] 冒泡排序

[NOI2022] 冒泡排序

题目背景

最近,小 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 所研究的序列均由非负整数构成。它的长度为 nn,且必须满足 mm 个附加条件。其中第 ii 个条件为:下标在 [Li,Ri][L_i, R_i] 中的数,即 aLi,aLi+1,,aRia_{L_i}, a_{L_{i+1}},\dots,a_{R_i} 这些数,其最小值恰好为 Vi\boldsymbol{V_i}

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

输入格式

本题有多组数据。

输入的第一行包含一个正整数 TT

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

接下来 mm 行,每行三个非负整数 Li,Ri,ViL_i, R_i, V_i,表示一组附加条件。数据保证 1LiRin1 \leq L_i \leq R_i \leq n0Vi1090 \leq V_i \leq 10^9

输出格式

输出共 TT 行,每行一个整数。

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

1
3 2
1 1 2022
2 3 39

1

提示

【样例解释 #1】

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

a2=39a_2 = 39,且 39a3<202239 \leq a_3 < 2022,则冒泡排序只有第一轮有交换操作,这一轮交换了 a1,a2a_1, a_2a2,a3a_2, a_3,总交换次数为 22

a2=39a_2 = 39,且 a32022a_3 \geq 2022,则冒泡排序只有第一轮有交换操作,这一轮仅仅交换 a1,a2a_1, a_2,总交换次数为 11

a3=39a_3 = 39,且 39<a2<202239 < a_2 < 2022,则冒泡排序算法第一轮交换 a1,a2a_1, a_2a2,a3a_2, a_3,第二轮交换 a1,a2a_1, a_2。总交换次数为 33

a3=39a_3 = 39,且 a22022a_2 \geq 2022,则冒泡排序算法第一轮交换 a2,a3a_2, a_3,第二轮交换 a1,a2a_1, a_2。总交换次数为 22

因此,交换次数的最小值为 11


【样例 #2】

见附件中的 bubble/bubble2.inbubble/bubble2.ans


【样例 #3】

见附件中的 bubble/bubble3.inbubble/bubble3.ans

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


【样例 #4】

见附件中的 bubble/bubble4.inbubble/bubble4.ans

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


【样例 #5】

见附件中的 bubble/bubble5.inbubble/bubble5.ans

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


【样例 #6】

见附件中的 bubble/bubble6.inbubble/bubble6.ans

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


【数据范围】

本题共 2525 个测试点。全部测试点满足:1T10001 \leq T \leq 10001n,m1061 \leq \sum n, \sum m \leq 10^61LiRin1 \leq L_i \leq R_i \leq n0Vi1090 \leq V_i \leq 10^9

其中 n,m\sum n, \sum m 分别表示所有测试点的 nn 的总和和 mm 的总和。n2,m2,n3,m3\sum n^2, \sum m^2, \sum n^3, \sum m^3 的含义类似。

测试点 数据范围 特殊性质
141 \sim 4 n,m7n,m \leq 7,且最多 22 组数据不满足 n,m5n, m \leq 5
575 \sim 7 n,m17n,m \leq 17,且最多 33 组数据不满足 n,m9n, m \leq 9 A
8108 \sim 10 n,m100n,m \leq 100n3,m34×107\sum n^3,\sum m^3 \leq 4 \times 10^7
111211 \sim 12 n,m2000n,m \leq 2000n2,m24×107\sum n^2,\sum m^2 \leq 4 \times 10^7
131413 \sim 14 B
151615 \sim 16 C
171817 \sim 18
1919 n,m106\sum n,\sum m \leq 10^6 A
2020 B
212221 \sim 22 C
232523 \sim 25

特殊性质 A:对于 1im1 \leq i \leq m0Vi10 \leq V_i \leq 1
特殊性质 B:对于 1im1 \leq i \leq mLi=RiL_i = R_i
特殊性质 C:输入给出的 mm 个区间 [Li,Ri][L_i, R_i] 两两不相交。


【提示】

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