自动搬运

查看原文

来自洛谷，原作者为

	C_Pos_Princess 这个家伙很懒，但留下了点什么

搬运于2025-08-24 22:44:28，当前版本为作者最后更新于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;
}