题目内容

在一座数据中心里，有一排编号从 $1$ 到 $n$ 的机柜，最初机柜之间没有任何网络连接。每天，管理员会进行一次操作：首先选定一段区间 $[l, r]$，并为所有满足 $l \le j < r$ 的整数 $j$ 在机柜 $j$ 与机柜 $j+1$ 之间建立一条双向网线（若已存在则忽略）。完成施工后，管理员想知道：从机柜 $x$ 出发，仅利用当前已有的网线，能够到达的机柜中编号最大的是多少。同一连通组内的机柜可以通过多段网线相互到达。

约束条件：

• 机柜总数 $n$ 满足 $2 \le n \le 10^9$；
• 操作天数 $m$ 满足 $1 \le m \le 10^6$；
• 对于每次操作，有 $1 \le l \le r \le n$，$1 \le x \le n$。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示机柜总数和操作天数。 接下来 $m$ 行，每行包含三个整数 $l, r, x$，依次表示该次操作中铺设网线的区间左端点、右端点，以及查询的起始机柜编号。

输出描述

输出共 $m$ 行，第 $i$ 行输出一个整数，表示第 $i$ 次操作完成后查询的结果。

样例1

输入

4 3
1 2 1
2 3 2
3 4 4

输出

2
3
4

说明

初始时没有任何连通块。 第一天：在 1 与 2 之间铺设网线，形成连通块 $[1,2]$。从 1 出发可达的最大编号为 2。 第二天：在 2 与 3 之间铺设网线，新区间 $[2,3]$ 与已有的 $[1,2]$ 在机柜 2 处重叠，合并为 $[1,3]$。从 2 出发可达的最大编号为 3。 第三天：在 3 与 4 之间铺设网线，再次合并得到 $[1,4]$。从 4 出发（已在连通块内）可达的最大编号为 4。

样例2

输入

10 3
2 5 7
6 8 7
1 10 1

输出

7
8
10

说明

第一天：在 2 到 5 之间铺设网线，形成连通块 $[2,5]$。查询机柜 7 不在任何连通块中，只能到达自身，答案为 7。 第二天：在 6 到 8 之间铺设网线，形成连通块 $[6,8]$，此时 $[2,5]$ 和 $[6,8]$ 是两个不连通的块。查询机柜 7 落在 $[6,8]$ 内，最右可达 8。 第三天：在 1 到 10 全部相邻点之间铺设网线，所有已有区间与新区间合并为一个 $[1,10]$。从 1 出发可达的最大编号为 10。

样例3

输入

2 1
1 2 1

输出

2

说明

只有 2 台机柜。在 1 和 2 之间铺设网线后，形成连通块 $[1,2]$。从 1 出发可到达的最大编号为 2。

视频试看，开通会员即可查看完整视频题解：1.题目讲解 2.思路分析 3.逐行代码手写