解题思路
核心思路
观察操作的本质：第 k 秒选择位置 x 时，若 x 与 x+1 颜色不同，则将 x 所在的整个同色区间染成 x+1 的颜色。这等价于将 x 所在连通块与 x+1 所在连通合并，合并时间为 k。
这提示我们使用 Kruskal 重构树 来维护连通块的合并过程：
- 构建重构树：初始时每个位置 i（1≤i≤n）为独立的叶子节点。遍历 t 次操作，第 k 次操作选择位置 x 时：
P4786.第3题-连连连
题目内容
有一排 n 个位置，从左到右编号为 1,2,…,n。每个位置都有一个 “颜色编号”（就是一个整数）。
一开始（记作第 0 秒），第 i 个位置的颜色为 i。
接下来会发生 t 次操作，按顺序依次执行。第 k 次操作（也就是第 k 秒）给出一个位置 x (保证 1≤x≤n−1)，并进行如下事情：
-
先找到一个最大区间 [L,R]，满足：
- L≤x≤R；
- 在第 k−1 秒结束后，区间 [L,R] 内所有位置的颜色都与位置 x 的颜色相同；
- [L,R] 不能再向左或向右扩展（也就是 L−1 或 R+1 的颜色与位置 x 不同，或者越界）。
-
然后，把区间 [L,R] 内所有位置的颜色，都改成 “位置 x+1 在第 k−1 秒结束后的颜色”。
现在有 q 次询问。每次询问给出一个区间 [l,r]，你需要回答：最早在第几秒（允许是第 0 秒），区间 [l,r] 内只存在一种颜色（也就是 l,l+1,…,r 这些位置的颜色全部相同）。如果直到第 t 秒都做完了也没发生，输出 −1。
输入描述
在一行上输入三个整数 n,t,q (2≤n,t,q≤2×105)，表示位置数量、操作次数、询问次数。
此后 t 行，每行输入一个整数 x (1≤x≤n−1)，表示这一秒选择的位置。
此后 q 行，每行输入两个整数 l,r (1≤l≤r≤n)，表示一次询问的区间。
输出描述
对于每个询问，新起一行输出一个整数，表示最早在第几秒区间 [l,r] 内只存在一种颜色。若不存在，输出 −1。
样例1
输入
5 4 5
4
3
2
1
1 5
2 5
3 5
1 1
1 2
输出
4
3
2
0
4
说明
第 0 秒颜色为 {1,2,3,4,5}。
第 1 秒选择 x=4，位置 4 的颜色段只有它自己，染成位置 5 的颜色后，颜色变为 {1,2,3,5,5}。
第 2 秒选择 x=3，颜色变为 {1,2,5,5,5}。
第 3 秒选择 x=2，颜色变为 {1,5,5,5,5}。
第 4 秒选择 x=1，颜色变为 {5,5,5,5,5}。
因此：
-
区间 [1,5] 最早在第 4 秒变成一种颜色；
-
区间 [2,5] 最早在第 3 秒变成一种颜色；
-
区间 [3,5] 最早在第 2 秒变成一种颜色；
-
区间 [1,1] 在第 0 秒就已经只有一种颜色；
-
区间 [1,2] 最早在第 4 秒变成一种颜色。
样例2
输入
4 2 4
3
3
1 4
3 4
2 3
2 2
输出
-1
1
-1
0
