team2012-B2-sol-0007

从 Trac 迁移的文章

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

原文章内容如下：

题意：给出N个数，然后有M个询问l,r问在第l个数到第r个数的区间内是否有数字重复。
思路：离线做，先将询问按照r进行升序排序，预处理出每个数字A[i]在他左边离他最近的重复数字的位置F[i]。从左往右扫，将F[i]送入树状数组，作r==i的询问，求出在树状数组中最大的一个数判断是不是>=l即可。

题意：给出N个数，然后有M个询问l,r问在第l个数到第r个数的区间内是否有数字重复。

思路：离线做，先将询问按照r进行升序排序，预处理出每个数字A[i]在他左边离他最近的重复数字的位置F[i]。从左往右扫，将F[i]送入树状数组，作r==i的询问，求出在树状数组中最大的一个数判断是不是>=l即可。