4358: 「JOI 2016 Final」断层

内存限制：256 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

**译者水平有限，跪求各位大佬提供更好的译文** **本题译自 [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 文明灭亡前哪一年的地层。

样例输入 复制 

10 2
12 1 3
2 2 2

样例输出 复制 

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\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|

来源/分类

提交提交记录统计讨论版露一手!