雪 / 雪球

题目链接：jzoj 7178 / luogu P7405

题目大意

给你一些球，有初始位置。
然后又一些操作，每次回将所有球左移或右移一定的长度。
当一个球经过两个相邻位置之间且它是第一个经过的，那它的分数会加一。
问你最后每个球的分数。

思路

首先我们要发现一个东西：无论你怎么跑，你两个球之间的相对位置是不变的，不会发生两个撞上的事情。
那我们可以不用记录每个点最后的位置，以及它每个时刻的位置，我们只需要记录它最左走了多少，最右走了多少。

那我们要处理什么呢？
我们也不难想到每个球得分的范围是一个区间，中间是不会空的。
那我们也不难看出左边左走，右边右走是没有限制的，可以直接看最远走了多远就走多远。

那我们接着看两个点之间领域的争夺。
那会分成两种，它们领域不会碰到，不会争夺，那就是最后最右走的长度减最后最左走的长度还小于等于两个点之间的位置，那就各自那各自的，能走多远拿多远。
拿如果会碰到呢？那我们就要看它们在什么地方碰到，那也可以求出它们占有的领域。

那怎么求在什么地方碰到呢？你不可以求出两个点每个时刻的位置。
但你不难想到延续前面的看是否碰到，你可以求出每个时刻的最左距离和最右距离，然后用这个来判断。
然后如果前一个时刻判断没有碰到，这个时刻判断碰到了，那就是这个时刻冲到了一起。
那当然不能直接枚举找，但你看到，前面都没有碰到，后面都碰到了，就可以二分出这个碰到的时间。
那你二分出来之后你要找碰的位置，也要分两种。
分别是它撞别人和别人撞他，这两个计算碰到位置的方法是不同的。
具体要怎么计算可以看看代码。

然后这么搞就可以了。

代码

#include<cstdio>
#include<iostream>
#define ll long long

using namespace std;

ll n, q, x[200001], L[200001], R[200001];
ll l[200001], r[200001], nowp, w[200001];
ll ans[200001];

int main() {
	scanf("%lld %lld", &n, &q);
	for (int i = 1; i <= n; i++) scanf("%lld", &x[i]);
	
	for (int i = 1; i <= q; i++) {
		scanf("%lld", &w[i]);
		nowp += w[i];
		L[i] = L[i - 1]; R[i] = R[i - 1];
		L[i] = min(L[i], nowp); R[i] = max(R[i], nowp);
	}
	
	ans[1] += -L[q];//最左边向左走，最右边向右走，没有限制
	ans[n] += R[q];
	for (int i = 2; i <= n; i++) {
		if (R[q] - L[q] <= x[i] - x[i - 1]) {//到最后都不会冲突
			ans[i - 1] += R[q];
			ans[i] += -L[q];
			continue;
		}
		ll left = 0, right = q, answ = q;//二分冲突的点
		while (left <= right) {
			int mid = (left + right) >> 1;
			if (R[mid] - L[mid] >= x[i] - x[i - 1]) answ = mid, right = mid - 1;
				else left = mid + 1;
		}
		//判断是自己冲过去撞了还是别人冲过来撞了
		//因为这两种情况要分别用两种方法计算
		//自己冲过去撞了要用别人的边界来计算，别人冲过来撞了就看自己的边界计算
		if (w[answ] < 0) ans[i - 1] += R[answ];
			else ans[i - 1] += x[i] + L[answ] - x[i - 1];
		if (w[answ] > 0) ans[i] += -L[answ];
			else ans[i] += x[i] - (x[i - 1] + R[answ]);
	}
	
	for (int i = 1; i <= n; i++)
		printf("%lld\n", ans[i]);
	
	return 0;
}