tkdsheep-solution-0007

从 Trac 迁移的文章

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

原文章内容如下：

{{{
这题做法应该比较多的，隔了太久都忘了自己是怎么做的了。。囧

看了一下代码，我用的是map+优先队列，map要维护一个娃娃最近一次出现的位置

先把查询区间按右端点从大到小排序

然后从右往左扫洋娃娃，比如扫到位置i，如果某个区间的右端点也是i就把区间push到优先队列里

然后对于每个位置i，如果这个洋娃娃最近一次出现的位置不是i（即之前已经出现过），假设这个位置是pos[i]

就从不断从优先队列抛出右端点最大的区间，看pos[i]是不是在这个区间内，在的话，那么这个区间的答案就是它

如果这个区间的左端点比i大，说明这个区间已经没用了，直接扔掉

整个复杂度nlogn
}}}

这题做法应该比较多的，隔了太久都忘了自己是怎么做的了。。囧
看了一下代码，我用的是map+优先队列，map要维护一个娃娃最近一次出现的位置
先把查询区间按右端点从大到小排序
然后从右往左扫洋娃娃，比如扫到位置i，如果某个区间的右端点也是i就把区间push到优先队列里
然后对于每个位置i，如果这个洋娃娃最近一次出现的位置不是i（即之前已经出现过），假设这个位置是pos[i]
就从不断从优先队列抛出右端点最大的区间，看pos[i]是不是在这个区间内，在的话，那么这个区间的答案就是它
如果这个区间的左端点比i大，说明这个区间已经没用了，直接扔掉
整个复杂度nlogn