小苯的回文询问(

 题目

离散化存储

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+9;
int n,q,ans[N],a[N];
map<int,int> mp;
vector<pair<int,int>>qr[N];
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=0;i<n;i++)cin>>a[i];
	vector<vector<pair<int,int>>> qr(n+2);
	for(int i=0,l,r;i<q;i++){
		cin>>l>>r;
		qr[r-1].push_back({l-1,i});
	}
	int l=-1;
	map<int,vector<int>>v;//?????????
	for(int i=0;i<n;i++){
		v[a[i]].push_back(i);
		int len=v[a[i]].size();
		if(v[a[i]].size()>=2){
			if(v[a[i]][len-1]>v[a[i]][len-2]+1)l=max(l,v[a[i]][len-2]);
		}
		if(v[a[i]].size()>=3)l=max(l,v[a[i]][len-3]);
		for(auto [L,p]:qr[i])ans[p]=L<=l;
	}
	for(int i=0;i<q;i++){
		if(ans[i])cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}