F题

本人太菜只配补题，分享一下补这道题目遇到的坑...

大致思路

好数组的定义为严格大于2，所以最少的回文串数量为3，也就是 111, 121这样子。

那么我们可以通过记录下标的方式来存储相同两个元素他们的下标差能否形成如题目所说的回文串的方式解决这个问题

我们先循环存储一遍（如样例所示）

1.第一次我们遇到了元素1，发现mp中不存在它，那么我们把它的位置存储到mp中。l数组是用来记录能够构成好数组的并且离当前位置最近的下标的位置，目前还没有好数组，所以l[1]存放0(因为后面询问的区间为1~1e9，所以0可以代表不符合)

2.第二个元素还是 1，那么我们发现mp中有它，但是相邻的两个数不符合题目好数组的定义，于是我们继续更新l[i]的最大值为0(还是不符合好数组)

3.第三个元素是2，mp中查询不到，存储mp[2] = 3，然后发现与前面的1 1 2还是构不成好数组，更新l[i] = 0

4.第四个元素是1, mp中查询为2，也就是离当前位置最近的2的范围内咱们可以构成一个回文串,所以这个时候l[i] = 2,代表距离最近的2~4可以构成好数组

...

最后查询的时,cin>>a>>b 如果l[b] >= a，那么说明在b位置标记的下标在最左值的范围内存在至少一对最近的回文串。

原本以为到这里就结束了，发现有一个样例卡住我，在大佬支招发现

9 1

1 1 2 1 1 1 1 2 2

4 7

这个样例会输出NO，所以说得加个特判，使得连续遇到三个以上的相同元素不会覆盖掉彼此的位置

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int a[N];
int l[N];
map<int, int> mp;
int main()
{
	int n, q;
	cin >> n >> q;
	for (int i = 1 ; i <= n ; i ++)
	{
		cin >> a[i];
		if (!mp[a[i]]) mp[a[i]] = i;
		if (mp[a[i]] and mp[a[i]] < i - 1) l[i] = mp[a[i]]; 
		l[i] = max(l[i],l[i - 1]);
		if (i > 2 and a[i] == a[i-2]) l[i] = i - 2; // 防止连续元素被覆盖的特判
		mp[a[i]] = i;
	}
	while(q --)
	{
		int a, b;
		cin >> a >> b;
		if (l[b] >= a) cout << "YES" << endl;
		else cout <<"NO" << endl;
	}
	return 0;
}