edward-solution-0007

从 Trac 迁移的文章

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

原文章内容如下：

令next[i]表示min{j | a[j] == a[i] && i < j}。然后问题变成求一个区间[l,r]内，从右边往左看，最早出现next[i] <= r的是哪一位。[[BR]]
于是把询问按l递减序排序，每个询问就去求next[i] <= r的i最大是多少。这个可以用树状数组维护。具体就是建立一棵下标是next[i]的树状数组，然后里面每个点的键值是i。

令next[i]表示min{j | a[j] == a[i] && i < j}。然后问题变成求一个区间[l,r]内，从右边往左看，最早出现next[i] <= r的是哪一位。

于是把询问按l递减序排序，每个询问就去求next[i] <= r的i最大是多少。这个可以用树状数组维护。具体就是建立一棵下标是next[i]的树状数组，然后里面每个点的键值是i。