team2012-D1-sol-0007

从 Trac 迁移的文章

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

原文章内容如下：

=== 解题思路 ===
给出一行上的 n 个数，再给出 m 个查询, 每次询问 [Li, Ri] 区间内最靠右的第二次出现的数字是多少.

这题我很土的用线段树来搞的, 线段树的做法需要对询问做一个排序, 因为询问需要在某些数没有插入线段树中时来做, 所以是一个离线算法, 比较麻烦. 赛后听了自然界学长讲了 O(n) 的解法, 学习了!

解题思路

给出一行上的 n 个数，再给出 m 个查询, 每次询问 [Li, Ri] 区间内最靠右的第二次出现的数字是多少.

这题我很土的用线段树来搞的, 线段树的做法需要对询问做一个排序, 因为询问需要在某些数没有插入线段树中时来做, 所以是一个离线算法, 比较麻烦. 赛后听了自然界学长讲了 O(n) 的解法, 学习了!