CF2030F RE on 11求助
  • 板块学术版
  • 楼主lrx___
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/20 20:49
  • 上次更新2024/10/20 22:20:26
查看原帖
CF2030F RE on 11求助
989792
lrx___楼主2024/10/20 20:49
#include <cstdio>
#include <algorithm>
#include <vector>
#include <list>

const int A(2e5+5);
bool vs[A];
int a[A],b[A],maxr[A],T,n,q,last[A];
std::list<int> tol[A],now;

int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d%d",&n,&q);
		now.clear();
		std::fill(vs+1,vs+n+1,false);
		std::fill(last+1,last+n+1,0);
		for(int i(1);i<=n;++i){
			scanf("%d",a+i);
			tol[i].clear();
			b[i]=last[a[i]];
			last[a[i]]=i;
		}
		for(int l(1),r(1);l<=n;++l){
			for(;r<=n&&!vs[a[r]];++r){
				if(b[r]<l){
					now.push_back(r);
				}else{
					for(;now.size()&&now.back()!=b[r];){
						vs[a[now.back()]]=true;
						tol[b[r]].push_front(now.back());
						now.pop_back();
					}
					now.pop_back();
					now.push_back(r);
				}
			}
			maxr[l]=r-1;
			for(auto& j:tol[l]){
				vs[a[j]]=false;
			}
			now.insert(now.begin(),tol[l].begin(),tol[l].end());
			tol[l].clear();
		}
		for(int i(0);i<q;++i){
			int l,r;
			scanf("%d%d",&l,&r);
			puts(maxr[l]>=r?"YES":"NO");
		}
	}
	return 0;
}
2024/10/20 20:49
加载中...