A6513. 「JSOI2018」列队
编程题
省选/NOI-
知识点
题目描述
作为一名大学生，九条可怜在去年参加了她人生中的最后一次军训。
军训中的一个重要项目是练习列队，为了训练学生，教官给每一个学生分配了一个休息位置。每次训练开始前，所有学生都在各自的休息位置休息，但是当教官发出集合命令后，被点到的学生必须要到指定位置集合。
为了简化问题，我们把休息位置和集合位置抽象成一根数轴。一共有 $n$ 个学生，第 $i$ 个学生的休息位置是 $a_i$。每一次命令，教官会指定一个区间 $[l,r]$ 和集合点 $K$ ，所有编号在 $[l,r]$ 内的学生都必须赶到集合点列队。在列队时，每一个学生需要选择 $[K,K+r-l]$ 中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标 $x$ 跑到坐标 $y$ 需要耗费体力 $|y-x|$ 。
在一天的训练中，教官一共发布了 $m$ 条命令 $(l,r,K)$ ，现在你需要计算对于每一条命令，在所有可能的列队方案中，消耗的体力值总和最小是多少。
以下是对题意的一些补充：
* 任何两条命令是无关的，即在一条集合命令结束后，所有学生都会回到自己的休息位置，然后教官才会发出下一条命令。
* 在集合的时候，可能有编号不在 $[l,r]$ 内的学生处在区间 $[K,K+r-l]$ 中，这时他会自己跑开，且跑动的距离不记在消耗的体力值总和中。
军训中的一个重要项目是练习列队，为了训练学生，教官给每一个学生分配了一个休息位置。每次训练开始前，所有学生都在各自的休息位置休息，但是当教官发出集合命令后，被点到的学生必须要到指定位置集合。
为了简化问题，我们把休息位置和集合位置抽象成一根数轴。一共有 $n$ 个学生，第 $i$ 个学生的休息位置是 $a_i$。每一次命令，教官会指定一个区间 $[l,r]$ 和集合点 $K$ ，所有编号在 $[l,r]$ 内的学生都必须赶到集合点列队。在列队时，每一个学生需要选择 $[K,K+r-l]$ 中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标 $x$ 跑到坐标 $y$ 需要耗费体力 $|y-x|$ 。
在一天的训练中，教官一共发布了 $m$ 条命令 $(l,r,K)$ ，现在你需要计算对于每一条命令，在所有可能的列队方案中，消耗的体力值总和最小是多少。
以下是对题意的一些补充：
* 任何两条命令是无关的，即在一条集合命令结束后，所有学生都会回到自己的休息位置，然后教官才会发出下一条命令。
* 在集合的时候，可能有编号不在 $[l,r]$ 内的学生处在区间 $[K,K+r-l]$ 中，这时他会自己跑开，且跑动的距离不记在消耗的体力值总和中。
输入格式
第一行输入两个整数 $n,m$。
第二行 $n$ 个整数 $a_i$ 表示学生的休息位置。保证学生休息的位置两两不同。
接下来 $m$ 行每行三个整数 $l,r,K$ 表示一条命令。
第二行 $n$ 个整数 $a_i$ 表示学生的休息位置。保证学生休息的位置两两不同。
接下来 $m$ 行每行三个整数 $l,r,K$ 表示一条命令。
输出格式
对于每一条命令输出一行一个整数表示最小的体力值总和。
输入输出样例
输入 #1
5 5 1 5 7 6 2 1 5 2 1 5 3 1 3 9 2 4 2 3 5 5
输出 #1
5 4 17 9 3
说明/提示
对于 $10\%$ 的数据，$n,m \leq 10$。
对于 $40\%$ 的数据，$n,m \leq 10^3$。
对于 $70\%$ 的数据，$n,m \leq 10^5$。
对于 $100\%$ 的数据，$n,m \leq 5 \times 10^5,1 \leq a_i,K \leq 10^6$。
对于 $100\%$ 的数据，学生休息的位置两两不同。
对于 $40\%$ 的数据，$n,m \leq 10^3$。
对于 $70\%$ 的数据，$n,m \leq 10^5$。
对于 $100\%$ 的数据，$n,m \leq 5 \times 10^5,1 \leq a_i,K \leq 10^6$。
对于 $100\%$ 的数据，学生休息的位置两两不同。