题解 P4559 【[JSOI2018]列队】

· · 题解

题意简述：

有 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;
}