自动搬运

查看原文

来自洛谷，原作者为

	小粉兔 Always continue; Never break;

搬运于2025-08-24 22:01:21，当前版本为作者最后更新于2019-01-11 19:04:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简述：

有 $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$ 种情况。

1. 这个区间中没有学生。直接返回 $0$。

2. 这个区间中的学生全部往右跑。返回 $(\sum k+rk_i-1)-(\sum a_i)$，左边是等差数列求和的形式，右边可以直接记。

3. 这个区间中的学生全部往左跑。返回 $(\sum a_i)-(\sum k+rk_i-1)$。

4. 不能确定这个区间中的学生的方向，递归到子树处理。

直接在主席树上实现即可。

时间复杂度 $O(n\log n+m\log n\times\text{wys})$，因为我不会分析递归的复杂度，可能是 $O(m\log n)$ 的。

#include <cstdio>

typedef long long LL;
const int MN = 500005;
const int MS = 11000005;

int n, m, s = 1000000;
int rt[MN];
int ls[MS], rs[MS], mx[MS], mn[MS], sz[MS], cnt;
LL sum[MS];

void Add(int &rt, int l, int r, int p) {
    ls[++cnt] = ls[rt], rs[cnt] = rs[rt], sz[cnt] = sz[rt] + 1, sum[cnt] = sum[rt] + p, rt = cnt;
    if (l == r) return ;
    int mid = l + r >> 1;
    if (p <= mid) Add(ls[rt], l, mid, p);
    else Add(rs[rt], mid + 1, r, p);
}

LL Qur(int rt1, int rt2, int l, int r, int f, int k) {
    if (!(sz[rt1] - sz[rt2])) return 0;
    LL Sz = sz[rt1] - sz[rt2], Sum = sum[rt1] - sum[rt2];
    if (l >= k + f) return Sum - (2*k + 2*f + Sz - 1) * Sz / 2;
    if (r <= k + f + Sz - 1) return (2*k + 2*f + Sz - 1) * Sz / 2 - Sum;
    int mid = l + r >> 1, lsz = sz[ls[rt1]] - sz[ls[rt2]];
    return Qur(ls[rt1], ls[rt2], l, mid, f, k) + Qur(rs[rt1], rs[rt2], mid + 1, r, f + lsz, k);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x; i <= n; ++i) {
        scanf("%d", &x);
        Add(rt[i] = rt[i - 1], 1, s, x);
    }
    for (int i = 1, l, r, k; i <= m; ++i) {
        scanf("%d%d%d", &l, &r, &k);
        printf("%lld\n", Qur(rt[r], rt[l - 1], 1, s, 0, k));
    }
    return 0;
}