当前位置:首页 > 莫队 > 正文
洛谷P5906【模板】回滚莫队&不删除莫队
127+

题目大意: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。下一个区间,我们可以充分利用之前的信息,先让右端点往右扩展,然后左端点往左扩展,不需要记录最左边出现的位置,因为后面需要回滚,而且记下来没有(不需要往右扩展);而最右边出现的位置,需要记录,因为可能两个数都在左边,回滚的时候,只要右端点在左边就清零即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,,

洛谷P5906【模板】回滚莫队&不删除莫队:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!