#P4559. [JSOI2018] 列队
[JSOI2018] 列队
题目描述
作为一名大学生,九条可怜在去年参加了她人生中的最后一次军训。
军训中的一个重要项目是练习列队,为了训练学生,教官给每一个学生分配了一个休息位置。每次训练开始前,所有学生都在各自的休息位置休息,但是当教官发出集合命令后,被点到的学生必须要到指定位置集合。
为了简化问题,我们把休息位置和集合位置抽象成一根数轴。一共有 个学生,第 个学生的休息位置是 。每一次命令,教官会指定一个区间 和集合点 ,所有编号在 内的学生都必须赶到集合点列队。在列队时,每一个学生需要选择 中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标 跑到坐标 需要耗费体力 。
在一天的训练中,教官一共发布了 条命令 ,现在你需要计算对于每一条命令,在所有可能的列队方案中,消耗的体力值总和最小是多少。
以下是对题意的一些补充:
-
任何两条命令是无关的,即在一条集合命令结束后,所有学生都会回到自己的休息位置,然后教官才会发出下一条命令。
-
在集合的时候,可能有编号不在 内的学生处在区间 中,这时他会自己跑开,且跑动的距离不记在消耗的体力值总和中。
输入格式
第一行输入两个整数 。
第二行 个整数 表示学生的休息位置。保证学生休息的位置两两不同。
接下来 行每行三个整数 表示一条命令。
输出格式
对于每一条命令输出一行一个整数表示最小的体力值总和。
5 5
1 5 7 6 2
1 5 2
1 5 3
1 3 9
2 4 2
3 5 5
5
4
17
9
3
提示
样例 1 解释
在第一条命令中,五名学生依次跑到 ,则总代价为 。
在第二条命令中,五名学生依次跑到 ,则总代价为 。
在第三条命令中,三名学生依次跑到 ,则总代价为 。
在第四条命令中,三名学生依次跑到 ,则总代价为 。
在第五条命令中,三名学生依次跑到 ,则总代价为 。
数据范围
对于 的数据,。
对于 的数据,。
对于 的数据,。
对于 的数据,。
对于 的数据,学生休息的位置两两不同。