题解：P9000 [CEOI2022] Measures

C_Pos_Princess · 2024-10-08 14:53:55 · 题解

题意

有 N 个站在数轴上的人，他们的初始位置分别为 a_1,a_2,\ldots,a_N，他们可以以 1 个单位长度每秒的速度移动。

因为众所周知的原因，他们需要保持社交距离，也就是说在任两个人之间距离至少为 D。

Alenka 设计了一个 app 来快速求出这 N 个人通过移动来保持社交距离的最小时间，现在她想要添加一个新功能：支持动态加入一个位置为 b_i 的人。

你需要实现一个程序完成这个功能。

题解

这种任意元素之间关系的题目，我们可以写成一种统一的形式。

让数组升序排列。对于任意的 i\le j，满足：

化简得到：

那最终的答案就是这个式子的最大值，相信很多题解都写了这个思路了，接下来我讲一下实现过程。

我们只需要维护出来这个差值，而这个值本身多少并不重要，所以在一个数字更新的时候，只会影响到前面位置的值，具体地也就是使前面位置的相对差值加上 D，这就变得非常好写。

这里注意这种情况的话 lazy 其实是不用下传的，只需要更新答案的时候加进去就好了。因为已经加入的数值也不会发生更改了。

代码

const int N = 1e6 + 10;
const int INF = 0x3f3f3f3f;
using namespace std;
struct node {
    int l, r;
    int minn, maxx;
    int num;
    int lazy;
} tr[N << 2];

int n, m, d;
void pushup(int rt) {
    tr[rt].minn = tr[rt].lazy + min(tr[rt << 1].minn, tr[rt << 1 | 1].minn);
    tr[rt].maxx = tr[rt].lazy + max(tr[rt << 1].maxx, tr[rt << 1 | 1].maxx);
    tr[rt].num = max(max(tr[rt << 1].num, tr[rt << 1 | 1].num), tr[rt << 1].maxx - tr[rt << 1 | 1].minn);
}

void build(int rt, int l, int r) {
    tr[rt].l = l;
    tr[rt].r = r;
    tr[rt].minn = INF;
    tr[rt].maxx = -INF;
    if (l == r) {
        return;
    }
    int mid =  l + r >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
}

void update(int rt, int x, int k) {
    if (tr[rt].l == tr[rt].r) {
        tr[rt].minn = tr[rt].maxx = k + tr[rt].lazy;
        return;
    }
    int mid = tr[rt].l + tr[rt].r >> 1;
    if (x <= mid) update(rt << 1, x, k);
    else {
        tr[rt << 1].maxx += d;
        tr[rt << 1].minn += d;
        tr[rt << 1].lazy += d;
        update(rt << 1 | 1, x, k);
    }
    pushup(rt);
}

int a[N];
pii s[N];
int id[N];
signed main() {

    read(n, m, d);
    for (int i = 1; i <= n + m; i++) {
        read(a[i]);
        s[i] = {a[i], i};
    }

    sort(s + 1, s + 1 + n + m);
    for (int i = 1; i <= n + m; i++)
        id[s[i].second] = i;

    build(1, 1, n + m);
    for (int i = 1; i <= n + m; i++) {
        update(1, id[i], a[i]);
        if (i > n) {
            write(tr[1].num / 2);
            if (tr[1].num & 1) printf(".5");
            SP;
        }
    }

    return 0;
}