洛谷P5906【模板】回滚莫队&不删除莫队
1360+
作者：crxis 发布：2022-02-17 分类：莫队
题目大意：n个数，m次询问，每次询问区间相同的数的最远间隔距离。
题目背景
这是一道模板题。
题目描述
给定一个序列，多次询问一段区间 $[l,r]$，求区间中**相同的数的最远间隔距离**。
序列中两个元素的**间隔距离**指的是**两个元素下标差的绝对值**。
输入输出格式
输入格式
第一行一个整数 $n$，表示序列长度。
第二行 $n$ 个整数，描述这个序列。
第三行一个整数 $m$，表示询问个数。
之后 $m$ 行，每行两个整数 $l,r$ 表示询问区间。
输出格式
共 $m$ 行，每行一个整数表示答案。如果区间内不存在两个数相同，则输出 $0$。
输入输出样例
输入样例 #1
8
1 6 2 2 3 3 1 6
5
1 4
2 5
2 8
5 6
1 7输出样例 #1
1
1
6
1
6
说明
记 $a_i$ 表示序列元素。
对于 $40\%$ 的数据，满足 $1\leq a_i \leq 400$，$1\leq n,m\leq 60000$。
对于 $100\%$ 的数据，满足 $1\leq n,m\leq 2\cdot 10^5$，$1\leq a_i\leq 2\cdot 10^9$。
解题思路
从左往右增加一个数，只需要跟这个数最左边出现的位置比较即可；从右往左增加一个数，只需要跟这个数最右边出现的位置比较即可。删除则很难出来，第一要找次大值，第二要更新他的临近位置。
对于维护最大值，我们可以用回滚莫队处理，对于更新位置，我们可以用链表维护，当然也有其他办法。
对于区间小的，我们可以暴力解决；对于区间大的，我们可以维护第二块值末尾[pi, y]的答案为ps。下一个区间，我们可以充分利用之前的信息，先让右端点往右扩展，然后左端点往左扩展，不需要记录最左边出现的位置，因为后面需要回滚，而且记下来没有（不需要往右扩展）；而最右边出现的位置，需要记录，因为可能两个数都在左边，回滚的时候，只要右端点在左边就清零即可。
程序实现
