#PQJ165x525. QOJ 165_525

    ID: 2689 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:JSOI 2018线段树

QOJ 165_525

军训列队 (line) 军训列队 (line) 【问题描述】 作为一名大学生,九条可怜在去年参加了她人生中的最后一次军训。 军训中的一个重要项目是练习列队,为了训练学生,教官给每一个学生分配 了一个休息位置。每次训练开始前,所有学生都在各自的休息位置休息,但是当 教官发出集合命令后,被点到的学生必须要到指定位置集合。 为了简化问题,我们把休息位置和集合位置抽象成一根数轴。一共有𝑛个学 生,第𝑖个学生的休息位置是𝑎%。每一次命令,教官会指定一个区间[𝑙, 𝑟]和集合点 𝐾,所有编号在[𝑙, 𝑟]内的学生都必须赶到集合点列队。在列队时,每一个学生需 要选择[𝐾, 𝐾+ 𝑟−𝑙]中的一个整数坐标站定且不能有任何两个学生选择的坐标 相同。学生从坐标𝑥跑到坐标𝑦需要耗费体力|𝑦−𝑥|。 在一天的训练中,教官一共发布𝑚条命令𝑙, 𝑟, 𝐾,现在你需要计算对于每一 条命令,在所有可能的列队方案中,消耗的体力值总和最小是多少。 补充解释: • 任何两条命令是无关的,即在一条集合命令结束后,所有学生都会回到 自己的休息位置,然后教官才会发出下一条命令。 • 在集合的时候,可能有编号不在[𝑙, 𝑟]内的学生处在区间[𝐾, 𝐾+ 𝑟−𝑙]中, 这时他会自己跑开,且跑动的距离不记在消耗的体力值总和中。 【输入格式】 第一行输入两个整数𝑛, 𝑚。 第二行𝑛个整数𝑎%表示学生的休息位置。保证学生休息的位置两两不同。 接下来𝑚行每行三个整数𝑙, 𝑟, 𝐾表示一条命令。 【输出格式】 对于每一条命令输出一行一个整数,表示完成该命令消耗体力值总和最小的 列队方案中,每个学生消耗的体力值之和。

军训列队 (line) 【样例输入】 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%的数据,𝑛, 𝑚≤10。 对于40%的数据,𝑛, 𝑚≤10J。 对于70%的数据,𝑛, 𝑚≤101。 对于100%的数据,𝑛, 𝑚≤5 ⋅101, 1 ≤𝑎%, 𝐾≤10L,学生休息位置两两不同。