题目内容

小红有一个长度为$n$的数组{$a_1,a_2,...,a_n$},数组初值全部为$0$，小红会进行$m$次操作，第$i$次操作为将区间$[l_i,r_i]$内的数全部修改为$i$。

现在小红拿到了$m$次操作之后的数组$a$，小红想知道每一次操作的区间$[l_i,r_i]$。

题目分析

给定一个长度为 $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$ 在最终数组中出现，则它的真实区间必包含这段连续区域，且可能被后续操作打断。
2. 填补未出现编号：对于没有在最终数组中出现的编号 $i$，说明操作 $i$ 的区间被后续所有操作完全覆盖。我们可以将其区间选在任意一个后续出现编号的区间内部。具体做法是对 $i$ 从 $m$ 递减到 $1$：