F 小苯的回文询问

题意

给定一个长为 n 的数组，给你 q 次询问，每次询问数组区间 [l, r] 中是否存在一个子序列满足其是一个长度大于 2 的回文子序列

思路

可以发现我们只需要考虑回文长度为 3 的回文子序列即可，因为大于 3 的回文子序列里面都包含着长度为 3 的子序列

我们对每一个数字都记下其上一次出现的位置的下标为 la[i]，如果没有则记为 0

因为题目要求回文子序列的长度至少为 3，所以记录的 la[i] 还存在 la[i] = i - 1 的情况。那么可以从后往前遍历整个 la 数组，令 la[i] = i - 1 的情况变为 la[i] = la[la[i]]。如此，la 数组的含义为：使得下标为 i 的数成为回文子序列的一部分的时候，左边界的位置。

那么怎么处理询问呢？相当于我们要在给定区间 [l, r] 中判断是否存在一个下标 i，满足 la[i] >= l && i <= r。那么是不是考虑 [l, r] 区间数组 la 的最大值即可？那么问题不久转化为了询问区间最大值吗？线段树等区间查询工具可以解决该问题。

另一种思路，我们对数组 la 取前缀 max，判断区间 [l, r] 是否满足条件即判断 la[r] >= l 即可。因为数组 la 存在一个前提条件：la[i] < i，所以，如果说满足 max{la[1 ~ r]} >= l，即意味着存在下标 i，满足 la[i] >= l && i >= l && i <= r，符合题意。所以也可以 解决这个问题。

代码

//Author: Qiansui
//Time: 2024-03-27 11:56
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x, y, sizeof(x))
#define debug(x) cout << #x << " = " << x << '\n'
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << '\n'
//#define int long long

using namespace std;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<double, double> pdd;
/*

*/
const int N = 2e5 + 5, inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f, mod = 998244353;

void solve(){
	int n, q;
	cin >> n >> q;
	vector<int> a(n + 1), la(n + 1);
	map<int, int> pos;
	for(int i = 1; i <= n; ++ i){
		cin >> a[i];
		la[i] = pos[a[i]];
		pos[a[i]] = i;
	}
	for(int i = n; i >= 1; -- i){
		if(la[i] == i - 1)
			la[i] = la[la[i]];
	}
	for(int i = 1; i <= n; ++ i)
		la[i] = max(la[i], la[i - 1]);
	while(q --){
		int l, r;
		cin >> l >> r;
		if(la[r] >= l) cout << "YES\n";
		else cout << "NO\n";
	}
	return ;
}

signed main(){
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int _ = 1;
	// cin >> _;
	while(_ --){
		solve();
	}
	return 0;
}