Problem Statement
小正方形亲眼看见了自己昔日的朋友被卷进了黑暗的深渊，然而它无力阻止……
现在它的朋友已经向它发起了攻击，因此小正方形不得不抵抗。
我们把山顶上的湖泊看作一条长度为 $m$ 的直线，一开始水深都在水平线上，我们视作此时的水深为 ‘0’
接下来，在一瞬间，小正方形的"朋友"们跳起并扎入水中，导致在入水点的水降低而远离入水点的水升高，注意两个 “朋友” 可能在同一地点入水。
小正方形的每个朋友有一个体积数值 $v$，当体积为 $v$ 的一个朋友跳入水中，我们设入水点为 $i$，将会导致 $i - v + 1$ 到 $i$ 的水位依次降低 $1,2,\cdots,v$
同样地，第 $i$ 到 $i + v - 1$ 的水位会依次降低 $v,v - 1,\cdots,1$.
相对应地，$i - v$ 的水位不变， $i - v - 1$ 到 $i - 2 * v$ 水位依次增加 $1,2,\cdots,v$， $i - 2 * v$ 到 $i - 3 * v + 1$ 水位依次增加 $v,v - 1,\cdots,1$
同样，$i + v$ 水位不变，$i + v + 1$ 到 $i + 2 * v$ 水位增加 $1,2,\cdots,v$，$i + 2 * v$ 到 $i + 3 * v - 1$ 水位依次增加 $v,v - 1,\cdots,1$
现在小正方形想要穿过这个湖，他想要知道在这 $n$ 个"朋友"跳入水中后湖上每个节点的水位，你能帮帮它吗？
第一行为两个整数 $n$,$m$，表示"朋友"的数目与湖泊的宽度。
接下来 $n$ 行，一行两个整数 $v,x$，表示第 $i + 1$ 个朋友的体积与入水点。
Output
一行 $m$ 个整数，第 $i$ 个整数表示 $i$ 号位的水深。
Sample Output #1
Sample Output #2
Constraints
对于 $30%$ 的数据，$n <= 50,m <= 500$
对于 $70%$ 的数据，$n <= 10^5,m <= 10^5$
对于 $100%$ 的数据，$n <= 10^6,m <= 10^6,1 <= v <= 10000,1 <= x <= m$
Solving
等差数列差分板子题，注意边界情况的讨论。
且要注意，在遇到题目中有类似$i - 3 * v + 1$这样的数据时，往往避免RE，我们将所有的数组元素整体右移一个很大的单位防止数组指针溢出导致WA，该题中为OFFSET。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include <bits/stdc++.h>
//#define int long long
#define endl '\n'
#define OFFSET 1000000//重要！
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N = 1e6*3+10;
ll diff[N];
const int M = 0;
int t;
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
int n,m;
cin >> n >> m;
//---------------------------------------------------
//等差数列差分模板
auto set = [&](int l,int r,int s,int e,int d)
{
diff[l+OFFSET] += s;
diff[l+1+OFFSET] += d - s;
diff[r+1+OFFSET] -= d + e;
diff[r+2+OFFSET] += e;
};
auto build = [&](int n)
{
for(int i=1;i<=n+OFFSET;i++) diff[i] += diff[i-1];
for(int i=1;i<=n+OFFSET;i++) diff[i] += diff[i-1];
};
//---------------------------------------------------
while(n--)
{
int v,i;
cin >> v >> i;
//注意转换边界条件，转换为L和R一左一右
set(i-v+1,i,-1,-v,-1);
set(i+1,i+v-1,-v+1,-1,1);
set(i-2*v,i-v-1,v,1,-1);
set(i-3*v+1,i-2*v-1,1,v-1,1);
set(i+v+1,i+2*v,1,v,1);
set(i+2*v+1,i+3*v-1,v-1,1,-1);
}
build(m);
for(int i=OFFSET+1;i<=m+OFFSET;i++) cout << diff[i] << ' ';
return 0;
}
|