#P5103. [JOI 2016 Final] 断层

[JOI 2016 Final] 断层

题目描述

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

本题译自 JOI 2016 Final T5「断層

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

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

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

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

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

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

输入格式

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

输出格式

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

10 2
12 1 3
2 2 2
3
3
5
5
5
5
5
5
2
2
10 6
14 1 1
17 1 1
-6 2 1
3 2 1
4 1 1
0 2 1
5
5
4
5
5
5
5
5
4
4
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
15
14
14
14
14
12
12
12
12
12
12
12
15
15
12

提示

样例解释 1

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,QN,Q 其他限制 分值
1 N,Q100N,Q\leqslant 100 $-100\leqslant X_i\leqslant 100, L_i=1(1\leqslant i\leqslant Q)$ 18
2 N,Q3000N,Q\leqslant 3000 16
3 N,Q2×105N,Q\leqslant 2\times10^5 66