题解 | #小明的区间#

#小明的区间

#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>z1,z2;//存区间的左右下标
int main(void)
{
	int n,k,L=0,R=0,Count=0;
	scanf("%d%d",&n,&k);
	int a[n+5],s[k+5];
	for(int i=0;i<n;i++)
		scanf("%d",&a[i]);
	memset(s,0,sizeof(s));
	while(R<n)
	{//采用双指针提前找好符合条件的区域
	//R快L慢，符合条件后慢指针走到不符合条件
	//然后快指针再走到符合条件，反复便可找到所有区域
		if(s[a[R]]==0)//因为ai<=k所以可以直接没走过的就计数，否则就再加个范围判断
			Count++;//刚开始的时候都是没走过的，走一种加一种
		s[a[R]]++;//踩过就能记录次数，不会重复count了
		while(Count==k)
		{//为什么要while因为可能2222231这样子一堆2要清
			//但这些区域我都要
			z1.push_back(L);
			z2.push_back(R);
			s[a[L]]--;
			if(s[a[L]]==0)
				Count--;//某种数清零成功了
			L++;//慢指针移动
		}
		R++;//快指针
	}
	/*
	for(int i=0;i<z1.size();i++)
	{
		for(int j=z1[i];j<=z2[i];j++)
			printf("%d ",a[j]);
		printf("\n");
	}
	*/
	int N;
	scanf("%d",&N);
	for(int i=0;i<N;i++)
	{
		int left,right;
		scanf("%d%d",&left,&right);
		left--;
		right--;
		//转换为数组下标
		//容器的二分的和普通的int数组调用形式有所区别的
		//返回的是指针，取值直接就是容器内的那个数了
		auto j=lower_bound(z1.begin(),z1.end(),left);
		//二分找到第一个在查询区域内的区域的左边
		if(j!=z1.end()&&*j<=right&&z2[j-z1.begin()]<=right)//且这个区域的右边也在里面
			printf("YES\n");
		else
			printf("NO\n");
		
	}
	return 0;
}