AT_abc364_f [ABC364F] Range Connect MST

题目描述

有一个包含 $N+Q$ 个顶点的图，顶点编号为 $1, 2, \ldots, N+Q$。初始时图中没有任何边。

对于该图，依次进行 $i=1,2,\ldots,Q$ 的如下操作：

• 对于每个满足 $L_i \leq j \leq R_i$ 的整数 $j$，在顶点 $N+i$ 与顶点 $j$ 之间添加一条无向边，边的代价为 $C_i$。

所有操作结束后，请判断该图是否连通。如果连通，请求出该图的最小生成树的总代价。

其中，最小生成树指的是所有顶点连通且边权和最小的生成树。

输入格式

输入按以下格式从标准输入读入。

$N$ $Q$
$L_1$ $R_1$ $C_1$
$L_2$ $R_2$ $C_2$
$\vdots$
$L_Q$ $R_Q$ $C_Q$

输出格式

如果图是连通的，输出最小生成树的总代价。否则输出 $-1$。

输入输出样例 #1

输入 #1

4 3
1 2 2
1 3 4
2 4 5

输出 #1

22

输入输出样例 #2

输入 #2

6 2
1 2 10
4 6 10

输出 #2

-1

输入输出样例 #3

输入 #3

200000 4
1 200000 1000000000
1 200000 998244353
1 200000 999999999
1 200000 999999999

输出 #3

199651870599998

说明/提示

限制条件

• $1 \leq N, Q \leq 2 \times 10^5$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq C_i \leq 10^9$
• 所有输入的值均为整数

样例解释 1

以下这些边构成了一个最小生成树：

• 顶点 $1$ 与 $5$ 之间的代价为 $2$ 的边
• 顶点 $2$ 与 $5$ 之间的代价为 $2$ 的边
• 顶点 $1$ 与 $6$ 之间的代价为 $4$ 的边
• 顶点 $3$ 与 $6$ 之间的代价为 $4$ 的边
• 顶点 $3$ 与 $7$ 之间的代价为 $5$ 的边
• 顶点 $4$ 与 $7$ 之间的代价为 $5$ 的边

$2+2+4+4+5+5=22$，因此输出 $22$。

样例解释 2

该图是不连通的。

由 ChatGPT 4.1 翻译