4364. [JSOI2018] 列队

【题目描述】

作为一名大学生，九条可怜在去年参加了她人生中的最后一次军训。

军训中的一个重要项目是练习列队，为了训练学生，教官给每一个学生分配了一个休息位置。每次训练开始前，所有学生都在各自的休息位置休息，但是当教官发出集合命令后，被点到的学生必须要到指定位置集合。

为了简化问题，我们把休息位置和集合位置抽象成一根数轴。一共有 $n$ 个学生，第 $i$ 个学生的休息位置是 $a_i$。每一次命令，教官会指定一个区间 $[l,r]$ 和集合点 $K$ ，所有编号在 $[l,r]$ 内的学生都必须赶到集合点列队。在列队时，每一个学生需要选择 $[K,K+r-l]$ 中的一个整数坐标站定且不能有任何两个学生选择的坐标相同。学生从坐标 $x$ 跑到坐标 $y$ 需要耗费体力 $\vert y-x \vert$ 。

在一天的训练中，教官一共发布了 $m$ 条命令 $(l,r,K)$ ，现在你需要计算对于每一条命令，在所有可能的列队方案中，消耗的体力值总和最小是多少。

以下是对题意的一些补充：

1.    任何两条命令是无关的，即在一条集合命令结束后，所有学生都会回到自己的休息位置，然后教官才会发出下一条命令。

2.    在集合的时候，可能有编号不在 $[l,r]$ 内的学生处在区间 $[K,K+r-l]$ 中，这时他会自己跑开，且跑动的距离不记在消耗的体力值总和中。

【输入格式】

第一行输入两个整数 $n,m$。

第二行 $n$ 个整数 $a_i$ 表示学生的休息位置。保证学生休息的位置两两不同。

接下来 $m$ 行每行三个整数 $l,r,K$ 表示一条命令。

【输出格式】

对于每一条命令输出一行一个整数表示最小的体力值总和。

【样例输入】

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

【样例说明】

在第一条命令中，五名学生依次跑到 $[2,5,4,6,3]$，则总代价为 $|2-1|+|5-5|+|4-7|+|6-6|+|3-2|=5$。 

在第二条命令中，五名学生依次跑到 $[4,5,7,6,3]$，则总代价为 $|4-1|+|5-5|+|7-7|+|6-6|+|3-2|=4$。 

在第三条命令中，三名学生依次跑到 $[11,10,9]$，则总代价为 $|11-1|+|10-5|+|9-7|=17$。 

在第四条命令中，三名学生依次跑到 $[4,2,3]$，则总代价为 $|4-5|+|2-7|+|3-6|=9$。 

在第五条命令中，三名学生依次跑到 $[7,6,5]$，则总代价为 $|7-7|+|6-6|+|5-2|=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\%$ 的数据，学生休息的位置两两不同。

【来源】

JSOI2018。