题目分析

1. 问题转化 题目要求在给定的区间 $[l, r]$ 中选出学生，让他们分别移动到目标区间 $[K, K + (r-l)]$ 中的每一个整数位置，使得移动的总距离（曼哈顿距离）最小。

根据贪心策略，为了使总移动距离最小，学生在原序列中的相对大小顺序应当保持不变。 即：区间 $[l, r]$ 中位置最小的学生去往目标 $K$，位置第二小的学生去往 $K+1$，以此类推。

假设区间 $[l, r]$ 内的学生按位置从小到大排序后的坐标为 $p_1, p_2, \dots, p_m$（其中 $m = r-l+1$），对应的目标位置为 $t_1, t_2, \dots, t_m$（其中 $t_i = K + i - 1$）。 我们需要计算的是：

2. 绝对值函数的性质 由于 $p_i$ 是单调递增的，$t_i$ 也是单调递增的，且 $t_i$ 的增长速度（斜率为1）通常小于等于 $p_i$ 的增长速度（因为原位置互不相同，至少 $+1$），$p_i - t_i$ 是单调不减的。 这意味着整个序列被分为三部分（可能缺失）：

1. 左侧部分：$p_i < t_i$，学生需要向右跑，代价为 $\sum (t_i - p_i)$。
2. 中间部分：$p_i = t_i$，代价为 0。
3. 右侧部分：$p_i > t_i$，学生需要向左跑，代价为 $\sum (p_i - t_i)$。

算法设计：主席树（可持久化线段树）

我们需要高效地查询区间 $[l, r]$ 内所有数值的信息。由于是静态区间查询，主席树（建立在值域上的可持久化线段树）是最佳选择。

主席树的每个节点维护两个信息：

• siz: 该值域区间内有多少个学生。
• num: 该值域区间内学生的位置坐标之和。

查询逻辑 (query 函数)

代码中的 query 函数极其精妙，它结合了线段树的区间性质和问题的单调性进行剪枝加速，避免了查找具体的“分界点”，而是整块处理。

函数签名：query(root_r, root_l_minus_1, val_l, val_r, start_k)

• x, y: 对应区间 $[l, r]$ 的主席树节点（前缀和思想）。
• l, r: 当前线段树节点覆盖的值域范围（例如 $0 \sim 10^6$）。
• z: 当前值域区间内的学生对应的起始目标位置。

核心逻辑流程：

1. 计算当前节点内的学生数： e = siz[x] - siz[y]。如果 e == 0，直接返回 0。 当前这 e 个学生的目标位置区间是 $[z, z + e - 1]$。

2. 情况一：全部向右跑 (All Move Right)

   判断条件：if (r <= z + e - 1)

   • 当前值域区间的最大值 r 小于等于目标区间的最大值 $z+e-1$。
   • 这意味着该节点内所有学生的位置 $p_i$ 都小于等于他们的目标位置 $t_i$（注意：虽然 $r$ 是值域上界，但严格证明利用了 $p_i - t_i$ 的单调性，这里是一个充分条件）。
   • 贡献计算：$\sum t_i - \sum p_i$。
   • $\sum t_i$ 是首项为 $z$，项数为 $e$ 的等差数列和：(z + z + e - 1) * e / 2。
   • $\sum p_i$ 是线段树维护的区间和：num[x] - num[y]。

3. 情况二：全部向左跑 (All Move Left) 判断条件：if (l >= z)

   • 当前值域区间的最小值 l 大于等于目标区间的最小值 $z$。
   • 这意味着该节点内所有学生的位置 $p_i$ 都大于等于他们的目标位置 $t_i$。
   • 贡献计算：$\sum p_i - \sum t_i$。
   • 即 (num[x] - num[y]) - (等差数列和)。

4. 情况三：递归分治 如果上述两种情况都不满足，说明在这个值域区间内，既有向左跑的，也有向右跑的（分界点在中间）。需要递归左右子树。

   • 左子树：目标起始位置不变，仍为 z。 query(son[x][0], son[y][0], l, mid, z)
   • 右子树：目标起始位置需要加上左子树的学生数量（因为左子树的学生占据了前 siz[left] 个目标位置）。 query(son[x][1], son[y][1], mid + 1, r, z + (siz[son[x][0]] - siz[son[y][0]]))

代码详细注释

#include <bits/stdc++.h>
using namespace std;

// 常用变量定义
int n, m;
const int kMaxN = 5e5 + 5;
// a: 初始位置
// root: 每个时间点的主席树根节点
// son: 左右孩子
// siz: 区间内数的个数
// tot: 节点总数
int a[kMaxN], root[kMaxN], son[kMaxN * 22][2], siz[kMaxN * 22], tot;
// num: 区间内数的总和 (注意要用 long long，防止溢出)
long long num[kMaxN * 22];

// 插入操作 (构建主席树)
// x: 当前节点, y: 上一版本的对应节点, l,r: 值域范围, z: 插入的数值
void insert(int x, int y, int l, int r, int z) {
    // 继承并更新信息
    siz[x] = siz[y] + 1;
    num[x] = num[y] + z;

    if (l == r) {
        return;
    }

    int mid = (l + r) / 2;

    if (z <= mid) {
        // 插入左子树，右子树复用上一版本
        son[x][0] = ++tot, son[x][1] = son[y][1];
        insert(tot, son[y][0], l, mid, z);
    } else {
        // 插入右子树，左子树复用上一版本
        son[x][1] = ++tot, son[x][0] = son[y][0];
        insert(tot, son[y][1], mid + 1, r, z);
    }
}

// 查询操作
// x: r版本的根, y: l-1版本的根, l,r: 值域范围, z: 当前处理的起始目标位置 K
long long query(int x, int y, int l, int r, int z) {
    // 如果区间内没有数，贡献为 0
    if (siz[x] == siz[y]) {
        return 0;
    }

    // e: 当前值域区间内的学生人数
    int e = siz[x] - siz[y];

    // 剪枝 1: 
    // 当前值域最大值 r <= 目标区间最大值 (z + e - 1)
    // 说明所有学生位置都偏小，都要向右跑
    if (r <= z + e - 1)
        // 代价 = 目标位置和 - 初始位置和
        // 目标位置和 = 等差数列求和 (首项 z, 末项 z+e-1, 项数 e)
        return (long long)(z + z + e - 1) * e / 2LL - (num[x] - num[y]);

    // 剪枝 2:
    // 当前值域最小值 l >= 目标区间最小值 z
    // 说明所有学生位置都偏大，都要向左跑
    if (l >= z)
        // 代价 = 初始位置和 - 目标位置和
        return (num[x] - num[y]) - (long long)(z + z + e - 1) * e / 2LL;

    // 无法整体判断，递归处理
    int mid = (l + r) / 2;
    // 左子树的人数
    int left_count = siz[son[x][0]] - siz[son[y][0]];
    
    // 递归左子树：目标起始位置还是 z
    // 递归右子树：目标起始位置变成 z + left_count (因为左子树的人占了前 left_count 个坑)
    return query(son[x][0], son[y][0], l, mid, z) + 
           query(son[x][1], son[y][1], mid + 1, r, z + left_count);
}

int main() {
    // IO 优化
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        // 动态开点，建立主席树，值域范围 0 ~ 1e6
        insert(root[i] = ++tot, root[i - 1], 0, 1e6, a[i]);
    }

    while (m--) {
        int l, r, x;
        cin >> l >> r >> x;
        // 查询区间 [l, r] 内的答案，起始目标位置为 x
        cout << query(root[r], root[l - 1], 0, 1e6, x) << '\n';
    }

    return 0;
}

复杂度分析

1. 空间复杂度： 主席树每次插入会新增 $\lceil \log_2(\text{值域}) \rceil$ 个节点。 值域为 $10^6$，$\log \approx 20$。 总空间为 $O(N \log (\max A_i))$。代码中开了 kMaxN * 22 是足够的。

2. 时间复杂度：

   • 构建：$O(N \log (\max A_i))$。
   • 查询：尽管是递归查询，但由于剪枝条件的存在，实际上只有包含“分界点”（$p_i \approx t_i$）的那一条路径会递归到底，其他分支会在 $O(1)$ 时间内返回。
   • 单次查询复杂度为 $O(\log (\max A_i))$。
   • 总时间复杂度为 $O((N + M) \log (\max A_i))$。

总结

这份代码通过主席树维护了区间内的数值信息，并利用问题的几何性质（单调性）在查询过程中进行剪枝，将原本可能复杂的计算转化为了简单的等差数列求和与区间和的减法，是非常经典且高效的解法。