#P17882. Yet Another MST Problem
Yet Another MST Problem
对于一个非负整数集合 ,定义 为不属于 的最小非负整数。
给定一个长度为 的排列 ,包含 各一次,以及 个闭区间 。
构造一张包含 个顶点的无向完全图,第 个顶点对应第 个区间。对于每一对不同顶点 ,它们之间的边权为这两个区间所包含的排列元素的并集的 MEX,即
$$w(i,j)=\operatorname{mex}\bigl(\{p_t\mid t\in[l_i,r_i]\cup[l_j,r_j]\}\bigr).$$求这张图的最小生成树的总权值。
输入格式
第一行两个整数 。
第二行 个整数 。
接下来 行,第 行两个整数 ,表示第 个区间。
输出格式
输出一个整数,表示最小生成树的总权值。
数据范围
- 。
- 是 的一个排列。
- 。
- 不同编号的区间可以完全相同,仍对应不同顶点。
样例 1
6 4
3 1 5 2 0 4
3 6
1 2
2 5
4 6
8
样例 2
2 2
0 1
1 2
1 2
2