记录编号	577228	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2022]冒泡排序	最终得分	100
用户昵称	李星昊	是否通过	通过
代码语言	C++	运行时间	13.832 s
提交时间	2022-10-27 15:04:43	内存使用	109.69 MiB

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read()
{
	re int t = 0;
	re char v = getchar();
	while (v < '0') {
		v = getchar();
	}
	while (v >= '0') {
		t = (t << 3) + (t << 1) + v - 48, v = getchar();
	}
	return t;
}
int t, n, m, a[1000002], A, B, L[1000002], R[1000002], V[1000002], W[1000002], mn[4000002], mnp[4000002], tg[4000002], fa[1000002], V1[1000002], V2[1000002], c[1000002], ans1, ans2;
char s[1000002];
inline void add(re int x)
{
	for (; x; x ^= x & (-x)) {
		++c[x];
	}
}
inline int ask(re int x, re int s = 0)
{
	for (; x <= m; x += x & (-x)) {
		s += c[x];
	}
	return s;
}
inline void build(re int p, re int l, re int r)
{
	tg[p] = mn[p] = 0, mnp[p] = l;
	if (l == r) {
		return;
	}
	re int mid = l + r >> 1;
	build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
}
inline void pu(re int p)
{
	mn[p] = min(mn[p << 1], mn[p << 1 | 1]);
	if (mn[p] == mn[p << 1]) {
		mnp[p] = mnp[p << 1];
	} else {
		mnp[p] = mnp[p << 1 | 1];
	}
}
inline void Add(re int x, re int y)
{
	mn[x] += y, tg[x] += y;
}
inline void pd(re int p)
{
	if (tg[p]) {
		Add(p << 1, tg[p]), Add(p << 1 | 1, tg[p]), tg[p] = 0;
	}
}
inline void add(re int p, re int l, re int r, re int x, re int y, re int z)
{
	if (l >= x && r <= y) {
		return Add(p, z);
	}
	pd(p);
	re int mid = l + r >> 1;
	if (x <= mid) {
		add(p << 1, l, mid, x, y, z);
	}
	if (y > mid) {
		add(p << 1 | 1, mid + 1, r, x, y, z);
	}
	pu(p);
}
inline void ask(re int p, re int l, re int r, re int x, re int y)
{
	if (l >= x && r <= y) {
		if (mn[p] < ans2) {
			ans2 = mn[p], ans1 = mnp[p];
		}
		return;
	}
	pd(p);
	re int mid = l + r >> 1;
	if (x <= mid) {
		ask(p << 1, l, mid, x, y);
	}
	if (y > mid) {
		ask(p << 1 | 1, mid + 1, r, x, y);
	}
}
struct node {
	int x, y;
	bool operator <(const node A)const
	{
		return x < A.x;
	};
};
inline int root(re int x)
{
	return x == fa[x] ? x : fa[x] = root(fa[x]);
}
vector<node>G[1000002];
int main()
{
	freopen("noi2022_bubble.in","r",stdin);
	freopen("noi2022_bubble.out","w",stdout);
	t = read();
	while (t--) {
		n = read(), m = read();
		for (re int i = 1; i <= m; ++i) {
			L[i] = read(), R[i] = read(), V[i] = W[i] = read(), G[i].clear();
		}
		for (re int i = 1; i <= n; ++i) {
			V1[i] = V2[i] = 0;
		}
		sort(W + 1, W + m + 1);
		for (re int i = 1; i <= m; ++i)V[i] = lower_bound(W + 1, W + m + 1, V[i]) - W, G[V[i]].push_back((node) {
			L[i], R[i]
		});
		for (re int i = 1; i <= n + 1; ++i) {
			fa[i] = i;
		}
		re bool ia = 1;
		for (re int i = m; i && ia; --i)if (G[i].size()) {
				sort(G[i].begin(), G[i].end());
				re int lst = n + 1;
				for (re int j = G[i].size() - 1; ~j && ia; --j)
					if (G[i][j].y < lst) {
						re int pos = root(G[i][j].x);
						V1[pos] = i, ia &= pos <= G[i][j].y, lst = pos;
					}
				for (auto z : G[i])
					for (re int j = root(z.x); j <= z.y; j = root(j)) {
						V2[j] = i, fa[j] = j + 1;
					}
			}
		if (!ia) {
			puts("-1");
			continue;
		}
		build(1, 0, m + 1);
		long long ans = 0;
		for (re int i = 1; i <= m; ++i) {
			c[i] = 0;
		}
		for (re int i = 1; i <= n; ++i)if (V1[i]) {
				ans += ask(V1[i] + 1), add(V1[i]), add(1, 0, m + 1, V1[i] + 1, m + 1, 1);
			}
		for (re int i = 1; i <= n; ++i)
			if (V1[i]) {
				add(1, 0, m + 1, V1[i] + 1, m + 1, -1), add(1, 0, m + 1, 0, V1[i] - 1, 1);
			} else {
				ans2 = 1e9, ask(1, 0, m + 1, V2[i], m + 1);
				ans += ans2;
				if (ans1) {
					add(1, 0, m + 1, 0, ans1 - 1, 1);
				}
			}
		printf("%lld\n", ans);
	}
}