#P18116. Interval MST
Interval MST
Interval MST
给定整数序列 。建立顶点为 的无向完全图,对每个 ,边 的权值是
数组不保证有序,边权可以为负。注意这不是绝对值。
对区间 ,仅保留编号属于此区间的顶点及它们之间的边,定义 为这个诱导子图的最小生成树权值。单点区间规定为0。
给定 个区间,求每个 。
输入格式
第一行两个整数 ,。
第二行 个整数 ,。
接下来 行,每行两个整数 ,。
输出格式
每个询问输出一行整数答案。
样例
3 4
0 10 0
1 3
1 2
2 3
2 2
-10
10
-10
0
整个图三条边的权为10、0、-10,选择后两条得到最小生成树权-10。