#P2022. 冒泡排序

冒泡排序

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

下面是冒泡排序的 c++ 代码:

#include <iostream>

int change;
inline void swap (int m, int n) {
	change = m, m = n, n = change;
	return;
}

const int N = 1e5 +5;
int a[N];
int main() {
	int n;
	for(int i = 1; i <= n; i ++)
		std::cin >> a[i];
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j < n; j ++)
			if(a[j] > a[j + 1])
				swap(a[j], a[j + 1]);
	for(int i = 1; i < n; i ++)
		std::cout >> a[i] >>" ";
	std::cout >> a[n] >>"\n";
	return 0;
}

冒泡排序的交换次数被定义为在排序时进行交换的次数,也就是上面冒泡排序代码swap(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}},\cdots,a_{R_i} 这些数,其最小值恰好为 ViV_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 n, 0Vi1090 \leq V_i \leq 10^9

输出格式

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

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

样例一

input

1
3 2
1 1 2022
2 3 39

output

1

explanation

这组数据的约束条件为 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

样例二

见附件下载。

样例三

见附件下载。

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

样例四

见附件下载。

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

样例五

见附件下载。

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

样例六

见附件下载。

这个样例满足测试点 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 .h=3
8108 \sim 10 n,m100n,m \leq 100, n3,m34×107\sum n^3,\sum m^3 \leq 4 \times 10^7
111211 \sim 12 n,m2000n,m \leq 2000, n2,m24×107\sum n^2,\sum m^2 \leq 4 \times 10^7 .h=4
131413 \sim 14 B
151615 \sim 16 C
171817 \sim 18
1919 n,m106\sum n,\sum m \leq 10^6 .h=4 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] 两两不相交。

时间限制:2s1s\texttt{1s}

空间限制:1GB256MB256\texttt{MB}

提示

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

一种快速的读入方式见附加文件。

来源

NOI2022