题目传送门：洛谷 P4559。
有 \(n\) 个学生，编号为 \(i\) 的学生有一个位置 \(a_i\)。
有 \(m\) 个询问，每次询问编号在 \([l,r]\) 区间内的学生跑到区间 \([k,k+r-l]\) 中的位置花费的距离总和的最小值。
每个学生的初始位置互不相同，最终到达的位置也必须互不相同。
不难证明，学生跑到最终的位置时，他们的相对位置不改变至少是最优解之一，这可以脑补一下。
所以我们只需要求最终相对位置不变时的答案即可。
因为学生两两位置不同，所以最终有一部分学生向右跑，有一部分学生向左跑。
向右跑的学生对答案的贡献是 \(k+rk_i-1-a_i\)，\(rk_i\) 表示他的位置在这个编号区间中的学生是第 \(rk_i\) 小的。
向左跑的学生对答案的贡献是 \(a_i-k-rk_i+1\)。
显然左边一部分学生向右跑，右边一部分学生向左跑。
考虑使用主席树处理这个问题。
对权值线段树进行可持久化，则编号区间内的学生就是两个线段树相减。
考虑递归进一个区间 \([l,r]\)，有 \(4\) 种情况。
这个区间中没有学生。直接返回 \(0\)。
这个区间中的学生全部往右跑。返回 \((\sum k+rk_i-1)-(\sum a_i)\)，左边是等差数列求和的形式，右边可以直接记。
这个区间中的学生全部往左跑。返回 \((\sum a_i)-(\sum k+rk_i-1)\)。
不能确定这个区间中的学生的方向，递归到子树处理。
直接在主席树上实现即可。
时间复杂度 \(O(n\log n+m\log n\times\text{wys})\)，因为我不会分析递归的复杂度，可能是 \(O(m\log n)\) 的。
洛谷 P4559: bzoj 5319: [JSOI2018]军训列队
原文：https://www.cnblogs.com/PinkRabbit/p/10256814.html