难度： 绿

算法： 莫队，数据结构

这题暂且不用莫队。

对于每个 $i$，令 $f_i$ 为最大的 $j$ 使得 $j>i$ 且 $a_i=a_j$。如果找不到则设为无穷大。预处理 $f$ 数组。

对于一个左端点为 $l$，右端点为 $r$ 的询问，我们只要看 $\min(f_l,f_{l+1},...,f_r)$ 与 $r$ 的大小关系。

如果有 $\min(f_l,f_{l+1},...,f_r)\le r$，那么就说明一定存在一个满足 $l\le p\le r$ 的 $p$ 使得 $f_p\le r$。此时，$a_p=a_{f_p}$ 且 $l\le p<f_p\le r$，答案为 No。

如果 $\min(f_l,f_{l+1},...,f_r)> r$，那么不存在一个 $p$ 满足 $l\le p\le r$ 且 $f_p<r$。如果 $[l,r]$ 中有两个相同的数，那么这两个数中靠左的一个的位置 $p$ 满足上述条件。但没有这样的 $p$，说明不存在两个相同的数，答案为 Yes。

使用线段树，ST 表等数据结构维护区间最小值，时间复杂度 $O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;
int n,m,a[100100],f[100100],l,r;
vector<int> v[100100];
int s[400400];
void push_up(int x){
	s[x]=min(s[2*x],s[2*x+1]);
}
void bu(int x,int le,int ri){
	if(le<ri){
		int mid=(le+ri)/2;
		bu(2*x,le,mid);
		bu(2*x+1,mid+1,ri);
		push_up(x);
	}
	else s[x]=f[le];
}
int que(int a,int b,int x,int le,int ri){
	if(a<=le&&ri<=b){
		return s[x];
	}
	int mid=(le+ri)/2;
	int res=1<<30;
	if(a<=mid) res=min(res,que(a,b,2*x,le,mid));
	if(b>mid) res=min(res,que(a,b,2*x+1,mid+1,ri));
	return res;
}
int main(){
	memset(f,0x3f3f3f,sizeof(f));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		v[a[i]].push_back(i);
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<int(v[i].size());j++){
			int u=v[i][j];
			if(j!=0){
				int w=v[i][j-1];
				f[w]=u;
			}
		}
	}
	bu(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&l,&r);
		int ans=que(l,r,1,1,n);
		if(ans<=r) printf("No\n");
		else printf("Yes\n");
	}
}