P4559 [JSOI2018] Lineup

As a university student, Jiutiao Kelian (pinyin) took part in the last military training of her life last year. An important task in the training is practicing lineups. To train the students, the instructor assigns each student a rest position. Before each training session starts, all students rest at their own rest positions. When the instructor gives the gathering command, the selected students must gather at the specified location. To simplify the problem, we model the rest positions and meeting positions as a number line. There are $n$ students, and the rest position of the $i$-th student is $a_i$. For each command, the instructor specifies an interval $[l, r]$ and a meeting point $K$. All students whose indices are in $[l, r]$ must rush to the meeting point to line up. During the lineup, each student must choose an integer coordinate in $[K, K + r - l]$ to stand on, and no two students may choose the same coordinate. If a student runs from coordinate $x$ to coordinate $y$, the stamina cost is $\vert y - x \vert$. During one day of training, the instructor issues $m$ commands $(l, r, K)$. For each command, you need to compute the minimum possible total stamina cost over all valid lineup assignments. Additional clarifications: 1. Any two commands are independent. That is, after one gathering command ends, all students return to their rest positions before the instructor issues the next command. 2. During gathering, there may be students whose indices are not in $[l, r]$ but are located within $[K, K + r - l]$. They will move away on their own, and their movement distance is not counted in the total stamina cost.

The first line contains two integers $n, m$. The second line contains $n$ integers $a_i$ representing the rest positions of the students. All rest positions are pairwise distinct. Each of the next $m$ lines contains three integers $l, r, K$ describing a command.

For each command, output one line with a single integer, the minimum total stamina cost.

$\,\boldsymbol{\text{Explanation for Sample 1}}$ In the first command, the five students run to $[2,5,4,6,3]$ respectively; the total cost is $|2-1|+|5-5|+|4-7|+|6-6|+|3-2|=5$. In the second command, the five students run to $[4,5,7,6,3]$ respectively; the total cost is $|4-1|+|5-5|+|7-7|+|6-6|+|3-2|=4$. In the third command, the three students run to $[11,10,9]$ respectively; the total cost is $|11-1|+|10-5|+|9-7|=17$. In the fourth command, the three students run to $[4,2,3]$ respectively; the total cost is $|4-5|+|2-7|+|3-6|=9$. In the fifth command, the three students run to $[7,6,5]$ respectively; the total cost is $|7-7|+|6-6|+|5-2|=3$. $\,\boldsymbol{\text{Constraints}}$ For $10\%$ of the testdata, $n, m \leq 10$. For $40\%$ of the testdata, $n, m \leq 10^3$. For $70\%$ of the testdata, $n, m \leq 10^5$. For $100\%$ of the testdata, $n, m \leq 5 \times 10^5$, $1 \leq a_i, K \leq 10^6$. For $100\%$ of the testdata, the students’ rest positions are pairwise distinct. Translated by ChatGPT 5