zrj2012-A3-0007

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：给出一个序列，每次会询问一个区间[l,r]问其中有没有数字重复，有则输出最后一组重复的数字。
PS：这里说明一下，题意是指，对区间[l,r]她想从右往左查询，如果发现有数字重复了，就立刻跳出，因此如果有一组重复（a1,a2）（a1在a2前），重复的位置应该是a1的位置（因为到a1时才知道有重复）
首先需要将数字离散化，以便构建一个桶（映射关系）来存放每一个数的信息（可以使用map）。
然后先从左往右扫描，记录每一个数最新出现的位置。对于每一个位置，我们可以通过o(1)的查询得知这个位置的数上一次出现的位置，即最近的重复。
然后我们再一次从左往右扫描，更新到每一个位置时，最近出现的一组重复的位置。这样对于每一组询问，我们只需要查询到r位置最近出现的一组重复的位置是不是在[l,r]之间就可以了。

题目大意：给出一个序列，每次会询问一个区间[l,r]问其中有没有数字重复，有则输出最后一组重复的数字。

PS：这里说明一下，题意是指，对区间[l,r]她想从右往左查询，如果发现有数字重复了，就立刻跳出，因此如果有一组重复（a1,a2）（a1在a2前），重复的位置应该是a1的位置（因为到a1时才知道有重复）

首先需要将数字离散化，以便构建一个桶（映射关系）来存放每一个数的信息（可以使用map）。

然后先从左往右扫描，记录每一个数最新出现的位置。对于每一个位置，我们可以通过o(1)的查询得知这个位置的数上一次出现的位置，即最近的重复。

然后我们再一次从左往右扫描，更新到每一个位置时，最近出现的一组重复的位置。这样对于每一组询问，我们只需要查询到r位置最近出现的一组重复的位置是不是在[l,r]之间就可以了。