#P4559. [JSOI2018] 列队

    ID: 4995 远端评测题 3000ms 500MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2018线段树各省省选递归江苏主席树

[JSOI2018] 列队

题目描述

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

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

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

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

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

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

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

输入格式

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

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

接下来 mm 行每行三个整数 l,r,Kl,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

提示

样例 1 解释

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

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

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

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

在第五条命令中,三名学生依次跑到 [7,6,5][7,6,5],则总代价为 77+66+52=3|7-7|+|6-6|+|5-2|=3

数据范围

对于 10%10\% 的数据,n,m10n,m \leq 10

对于 40%40\% 的数据,n,m103n,m \leq 10^3​​。

对于 70%70\% 的数据,n,m105n,m \leq 10^5​​。

对于 100%100\% 的数据,n,m5×105,1ai,K106n,m \leq 5 \times 10^5,1 \leq a_i,K \leq 10^6​​。

对于 100%100\% 的数据,学生休息的位置两两不同。