AT_joi2016ho_e.断層 (Geologic Fault)

很久以前，存在着一个高度发达的文明，被称为 IOI 文明。然而，由于火山喷发，这个高度发达的文明最终灭亡了。IOI 文明沿着一条直线状的河流繁荣发展，在 IOI 文明灭亡时，其地表是平坦的。IOI 文明的遗址可以视为坐标平面上的 $x$ 轴，$y$ 轴表示高度方向。也就是说，在坐标平面中，直线 $y=0$ 表示地表，区域 $y>0$ 表示地上，区域 $y<0$ 表示地下。此外，IOI 文明灭亡时，$a$ 年前（$a\geq 0$）的地层位于直线 $y=-a$ 的位置。

在 IOI 文明灭亡后，遗址上发生了 $Q$ 次地壳变动。第 $i$ 次（$1\leq i\leq Q$）地壳变动由位置 $X_i$、方向 $D_i$、变动量 $L_i$ 表示。$D_i$ 为 $1$ 或 $2$。第 $i$ 次地壳变动按如下方式发生：

• 地层的移动如下：
  • 当 $D_i=1$ 时，断层沿过点 $(X_i,0)$、斜率为 $1$ 的直线形成，该直线之上的地层沿直线方向上升 $L_i$ 的高度。即，该直线之上的点 $(x, y)$ 移动到点 $(x+L_i, y+L_i)$。
  • 当 $D_i=2$ 时，断层沿过点 $(X_i,0)$、斜率为 $-1$ 的直线形成，该直线之上的地层沿直线方向上升 $L_i$ 的高度。即，该直线之上的点 $(x, y)$ 移动到点 $(x-L_i, y+L_i)$。
• 紧接着，区域 $y>0$ 的地层因风化全部消失。

时光流转至现代，考古学家 JOI 博士开始发掘 IOI 文明的遗迹。JOI 博士想知道每个位置的地表地层，是 IOI 文明灭亡前多少年的地层。已知所有地壳变动的情况。你的任务是，代替 JOI 博士，对于每个满足 $1\leq i\leq N$ 的整数 $i$，求出点 $(i-1,0)$ 与点 $(i,0)$ 之间的地表地层，是 IOI 文明灭亡前多少年的地层。

从标准输入读取如下内容。

• 第 $1$ 行包含两个整数 $N, Q$，用空格分隔。表示需要求解的地点数量为 $N$，地壳变动的次数为 $Q$。
• 接下来的 $Q$ 行中，第 $i$ 行（$1\leq i\leq Q$）包含三个整数 $X_i, D_i, L_i$，用空格分隔。表示第 $i$ 次地壳变动的位置为 $X_i$，方向为 $D_i$，变动量为 $L_i$。

输出共 $N$ 行。第 $i$ 行（$1\leq i\leq N$）输出点 $(i-1,0)$ 与点 $(i,0)$ 之间的地表地层，是 IOI 文明灭亡前多少年的地层的整数。

任务

已知 IOI 文明遗址上发生的所有地壳变动，对于每个整数 $i$（$1\leq i\leq N$），输出点 $(i-1,0)$ 与点 $(i,0)$ 之间的地表地层，是 IOI 文明灭亡前多少年的地层。

限制

所有输入数据满足以下条件：

• $1\leq N\leq 200\,000$。
• $1\leq Q\leq 200\,000$。
• $-1\,000\,000\,000\leq X_i\leq 1\,000\,000\,000$（$1\leq i\leq Q$）。
• $1\leq D_i\leq 2$（$1\leq i\leq Q$）。
• $1\leq L_i\leq 1\,000\,000\,000$（$1\leq i\leq Q$）。

子任务

子任务 1 [18 分]

满足以下条件：

• $N\leq 100$。
• $Q\leq 100$。
• $-100\leq X_i\leq 100$（$1\leq i\leq Q$）。
• $L_i=1$（$1\leq i\leq Q$）。

子任务 2 [16 分]

满足以下条件：

• $N\leq 3,000$。
• $Q\leq 3,000$。

子任务 3 [66 分]

无额外限制。

样例说明 1

该输入示例对应下图。

样例说明 2

该输入示例满足子任务 $1$ 的限制。

由 ChatGPT 4.1 翻译