解题思路

这道题的关键在于发现： 铁路只会在相邻城市之间修建，并且每天修建的是一整段连续区间 $[l_i,r_i]$ 内的所有相邻边。

因此，任意时刻整张图的每个连通块一定都对应为一段连续的城市区间。

也就是说，我们只需要维护若干个两两不相交的区间 $[L,R]$，表示当前哪些城市已经连成了一个连通块。

题目内容

在遥远的某个大陆上，有一个国家由 $n$ 个城市组成，编号为 $1,2,...,n$ 。国王计划在接下来的 $m$ 天内修建铁路。

在第 $i$ 天，工匠会首先在城市 $l_i$ 到 $r_i$ 之间的所有相邻城市对之间修建双向铁路；换句话说，对于所有满足 $l_i≤j_i<r_i$ 的整数 $j$ ，在城市 $j$ 与城市 $j+1$ 之间修建一条双向铁路。

修建完成后，国王想知道，在当前所有已修建铁路的条件下，从城市 $x_i$ 出发能到达的最大城市编号。

初始时不存在任何铁路；后续各天的修建在已修基础上累积生效。

输入描述

第一行输入两个整数 $n,m(2≤n≤10^9;1≤m≤10^6)$ 分别表示城市数量和修建天数。

接下来 $m$ 行，每行输入三个整数 $l_i,r_i,x_i(1≤l_i≤r_i≤n;1≤x_i≤n)$ 表示第 $i$ 天的操作：

在城市，$l_i$ 到 $r_i$ 之间的所有相邻城市对之间修建双向铁路。

查询从城市 $x_i$ 出发能到达的最大城市编号。

输出描述

输出共 $m$ 行，第 $i$ 行输出一个整数，表示第 $i$ 天从 $x_i$ 出发可到达的最大城市编号。

样例1

输入

5 3
1 3 2
2 5 1
1 5 4

输出

3
5
5

说明

第一天，修建城市 $1-2$ 与 $2-3$ 的铁路，连通块变为 {$1,2,3$}，从城市 $2$ 出发可到达的最大城市编号为 $3$ ；

第二天，修建城市 $2-5$ 间的铁路 $(2-3,3-4,4-5)$，连通块扩展为 {$1,2,3,4,5$}，从城市 $1$ 出发可到达的最大城市编号为 $5$；

第三天，修建城市 $1-5$ 间的所有铁路(已全连通)，连通块仍为 {$1,2,3,4,5$}，从城市 $4$ 出发可到达的最大城市编号为 $5$。

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