[JOI 2016 Final] 断层
题目描述
**译者水平有限,跪求各位大佬提供更好的译文**
**本题译自 [JOI 2016 Final](https://www.ioi-jp.org/joi/2015/2016-ho/index.html) T5「[断層](https://www.ioi-jp.org/joi/2015/2016-ho/2016-ho.pdf)」**
很久很久以前,一个叫做 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
输入样例 #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
![0fe14625e2fb78233cfd864dde8e1eda.png](http://www.z4a.net/images/2018/02/09/0fe14625e2fb78233cfd864dde8e1eda.png)
#### 数据范围与提示
对于所有数据,$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|