题目分析

给定一个长度为 $n$ 的初始全零数组，进行了 $m$ 次区间赋值操作，第 $i$ 次操作将区间 $[l_i, r_i]$ 内的所有元素赋值为 $i$。我们仅给出最终数组 $a$，要求还原每一次操作的区间 $[l_i, r_i]$。

• 数组长度和操作次数均可达 $10^5$，需 $O(n + m)$ 或 $O((n + m) \log n)$ 复杂度。
• 操作会互相覆盖，后面的操作会覆盖前面的值，最终数组中某些值可能完全被覆盖而不出现。
• 数据保证存在解。

解题思路

1. 记录出现区间：对每个操作编号 $i$，在最终数组中记录它第一次出现的位置为 $\mathrm{L}[i]$，最后一次出现的位置为 $\mathrm{R}[i]$。如果某 $i$ 在最终数组中出现，则它的真实区间必包含这段连续区域，且可能被后续操作打断。