[AdditionalFile3469.zip](file://AdditionalFile3469.zip?type=additional_file)

P7405 [JOI 2021 Final] 雪球 / Snowball

题目描述

在一条无限长的数轴上，有 $N$ 个雪球，这 $N$ 个雪球编号为 $1 \sim N$，第 $i$ 个雪球在第 $A_i$ 个点上。刚开始，整条数轴覆盖满了雪，接下来 $Q$ 天将会刮起大风，第 $j$ 天的风力强度为 $W_j$，如果 $W_j$ 为正数，所有雪球都朝右移动 $W_j$ 个单位长度，如果 $W_j$ 为负数，所有雪球都朝左移动 $-W_j$ 个单位长度。

当一个区间 $[a,a+1]$ 被雪覆盖时，雪球滚上去雪球的质量会加一，这一个区间里的雪也会被清空。刚开始每一个雪球的质量均为 $0$，而这 $Q$ 天里也没有再下雪。

你想问这 $Q$ 天结束后每个雪球的质量是怎样的。

输入格式

第一行两个整数 $N,Q$ 代表雪球个数和下雪天数。

第二行 $N$ 个整数 $A_i$ 代表这 $N$ 个雪球的初始位置。

接下来 $Q$ 行每行一个整数 $W_j$ 代表每一天的风力强度。

输出格式

$N$ 行每行一个整数代表这 $Q$ 天结束后每一个雪球的质量。

输入输出样例 #1

输入 #1

4 3
-2 3 5 8
2
-4
7

输出 #1

5
4
2
6

输入输出样例 #2

输入 #2

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

输出 #2

3000000000000

输入输出样例 #3

输入 #3

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

输出 #3

14
8
7
9
11
10
9
8
5
10

说明/提示

样例 1 解释

雪球初始位置为 $-2,3,5,8$，初始质量为 $0,0,0,0$。

• 第一天过后，雪球位置为 $0,5,7,10$，质量为 $2,2,2,2$。
• 第二天过后，雪球位置为 $-4,1,3,6$，质量为 $4,4,2,3$。
• 第三天过后，雪球位置为 $3,8,10,13$，质量为 $5,4,2,6$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（33 pts）：$N,Q \le 2000$。
• Subtask 2（67 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N,Q \le 2 \times 10^5$，$|A_i|,|W_j| \le 10^{12}$，$A_i<A_{i+1}$。

说明

翻译自 The 20th Japanese Olympiad in Informatics Final Round B 雪玉的英文翻译 Snowball。

#3469. 「JOI 2021 Final」雪球

标签: 传统 | 时间限制: 3000 ms | 内存限制: 512 MiB |

题目描述

译自 JOI 2021 Final T2「雪玉 / Snowball」

JOI 平原是一个东西延伸的大平原。我们可以把 JOI 平原看做一个数轴。在 JOI 平原上的一点用坐标表示。数轴的正方向表示东向。现在是 JOI 平原的冬天。在 JOI 平原上有 $N$ 个雪球，自西向东从 $1$ 到 $N$ 编号。最初，雪球 $i\ (1\le i\le N)$ 的坐标是 $X_i$。

在冬季，JOI 平原上会刮起强风。你有 $Q$ 天的对风的观测数据。在第 $j\ (1\le j\le Q)$ 天，风用一个整数 $W_j$ 表示。如果 $W_j$ 是负数，那么风向西吹，否则风向东吹。风力强度是 $|W_j|$。

刮风时，雪球也沿风吹的方向滚动，移动的距离就等于风力强度。换句话说，如果第 $j$ 天开始的时候，有一个雪球位于坐标为 $x$ 的位置，那么这个雪球就会从 $x$ 移向 $x+W_j$ 位置。在第 $j$ 天结束时，这个雪球就位于坐标为 $x+W_j$ 的位置了。注意，在每天，雪球都同时移动，移动速度也相同。

最初，JOI 平原被雪覆盖。如果一个雪球在一个被雪覆盖的区间上滚过去，这些雪就会被滚在雪球上，雪球的质量会增加，并且这个区间内的雪就会消失。换句话说，对于一个整数 $a$，假设从 $a$ 到 $a+1$ 的区间被雪覆盖。如果一个雪球从这个区间滚过去，那么雪球的质量就会增加 $1$，从 $a$ 到 $a+1$ 的区间上的雪会消失。如果雪球从一个没有雪的区间上滚过去，那么雪球的质量不变。

最初，每个雪球的质量都是 $0$。在这 $Q$ 天的观测中都没有下雪。

你想知道在第 $Q$ 天结束后每个雪球的质量。

给出每个雪球的位置和这 $Q$ 天对风的观测数据，写一个程序计算在第 $Q$ 天结束后每个雪球的质量。

输入格式

第一行两个整数 $N,Q$；

第二行 $N$ 个整数 $X_i$，表示雪球的初始位置；

接下来 $Q$ 行，每行一个整数 $W_i$，表示这 $Q$ 天的观测数据。

输出格式

输出 $N$ 行，第 $i\ (1\le i\le N)$ 行输出雪球 $i$ 在第 $Q$ 天结束后的质量。

样例 1

输入

4 3
-2 3 5 8
2
-4
7

输出

5
4
2
6

在这组输入中，每个雪球的质量如下变化：

• 初始时，雪球的坐标自西向东分别为 $-2,3,5,8$。雪球的质量分别为 $0,0,0,0$。
• 第一天，风向东吹，强度为 $2$，在第一天结束时，雪球的坐标分别为 $0,5,7,10$，雪球的质量分别为 $2,2,2,2$。
• 第二天，风向西吹，强度为 $4$，在第二天结束时，雪球的坐标分别为 $-4,1,3,6$，雪球的质量分别为 $4,4,2,3$。
• 第三天，风向东吹，强度为 $7$，在第三天结束时，雪球的坐标分别为 $3,8,10,13$，雪球的质量分别为 $5,4,2,6$。

样例 2

输入

1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000

输出

3000000000000

样例 3

输入

10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6

输出

14
8
7
9
11
10
9
8
5
10

数据范围与提示

对于全部数据，满足：

• $1\le N,Q\le 2\times 10^5$；
• $|X_i|,|W_j|\le 10^{12}\ (1\le i\le N,1\le j\le Q)$；
• $X_i<X_{i+1}\ (1\le i\le N-1)$。

子任务附加限制及分值如下：

• 子任务 1（$33$ 分）：$N,Q\le 2\ 000$；
• 子任务 2（$67$ 分）：无附加限制。