#2346. 「JOI 2016 Final」断层

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

译者水平有限,跪求各位大佬提供更好的译文

本题译自 JOI 2016 Final T5「断層

很久很久以前,一个叫做 IOI 的先进文明蓬勃发展。时过境迁,现代考古学家 JOI 博士决定挖掘 IOI 文明遗址。

IOI 文明沿着笔直的河流发展。方便起见,IOI 文明遗址可以看作平面直角坐标系的 x 轴,而 y 轴表示海拔。IOI 文明地面平坦,也就是说,直线 y=0 代表地面,而 y>0 代表地面上空, y<0 代表地下。另外,由于流水堆积,IOI 文明的地面一直在缓慢升高。IOI 文明灭亡前 a (a\geqslant 0) 时,直线 y=-a 才是地平面。
IOI 文明灭亡后,它脚下的地层发生了 Q 次运动。第 i 次运动 (1\leqslant i\leqslant Q) 可用位置 X_i ,方向 D_i 和变化量 L_i 描述。 D_i = 1 2 。具体来说,

  • D_i=1 :断层视为一条过 (X_i, 0) ,斜率为 1 的直线。断层上方的地层斜向上移动,横坐标增加 L_i ,纵坐标增加 L_i 。也就是说,直线上方的所有点 (x,y) 移动到 (x+L_i, y+L_i)
  • D_i=2 :断层视为一条过 (X_i, 0) ,斜率为 -1 的直线。断层上方的地层斜向上移动,横坐标减少 L_i ,纵坐标增加 L_i 。也就是说,直线上方的所有点 (x,y) 移动到 (x-L_i, y+L_i)

每次地壳运动后, y>0 的地层都会因风化作用而消失。

试求:对于每一个 i(1\leqslant i\leqslant N) (i-1,0) 和 点 (i,0) 之间的地层是在 IOI 文明灭亡前哪一年的地层。

y 轴上,断层都是经过整点的, y 轴上的相邻整点间没有断层。这样讲能明白吧……

输入格式

第一行有两个整数 N,Q ,用空格分隔。
在接下来的 Q 行中,第 i (1\leqslant i\leqslant N) 有三个整数 X_i, D_i, L_i ,用空格分隔。
输入的所有数的含义见题目描述。

输出格式

输出共 N 行,第 i (1\leqslant i\leqslant N) 有一个整数,表示点 (i-1,0) 和 点 (i,0) 之间的地层是在 IOI 文明灭亡前哪一年的地层。

样例

输入样例 1

10 2
12 1 3
2 2 2

输出样例 1

3
3
5
5
5
5
5
5
2
2

样例解释 1

0fe14625e2fb78233cfd864dde8e1eda.png

输入样例 2

10 6
14 1 1
17 1 1
-6 2 1
3 2 1
4 1 1
0 2 1

输出样例 2

5
5
4
5
5
5
5
5
4
4

输入样例 3

15 10
28 1 7
-24 2 1
1 1 1
8 1 1
6 2 1
20 1 3
12 2 2
-10 1 3
7 2 1
5 1 2

输出样例 3

15
14
14
14
14
12
12
12
12
12
12
12
15
15
12

数据范围与提示

对于所有数据, 1\leqslant N, Q\leqslant 2\times 10^5, -10^9\leqslant X_i\leqslant 10^9, D_i=1 2, 1\leqslant L_i\leqslant 10^9(1\leqslant i\leqslant Q)

Subtask # N,Q 其他限制 分值
1 N,Q\leqslant 100 -100\leqslant X_i\leqslant 100, L_i=1(1\leqslant i\leqslant Q) 18
2 N,Q\leqslant 3000 16
3 N,Q\leqslant 2\times10^5 66