洛谷 P 3901

大概题意:给你n个数字,然后q次查询,问每个区间的数字是否都互不相同。
输出格式
对每个询问输出一行,“Yes” 或者“No”

输入输出样例
输入 #1 复制
4 2
1 2 3 2
1 3
2 4
输出 #1 复制
Yes
No
说明/提示

1<= n ,q <=1e5 。


比较简单的一道题。


直接莫队即可。因为显然具有区间可加性(权值线段树也可以)。


然后我们对查询排序,就可以了

AC代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,q,vis[N],res[N],a[N],cnt,bl,cl,cr;
struct node{
	int l,r,id;
}t[N];
int cmp(const node &s1,const node &s2){
	return (s1.l/bl==s2.l/bl)?(s1.r<s2.r):(s1.l<s2.l);
}
inline void del(int pos){
	if(!(--vis[a[pos]]))	cnt--;
}
inline void add(int pos){
	if((++vis[a[pos]])==1)	cnt++;
}
signed main(){
	scanf("%d %d",&n,&q);	bl=sqrt(n);
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
	for(int i=1;i<=q;i++)	scanf("%d %d",&t[i].l,&t[i].r),t[i].id=i;
	sort(t+1,t+1+q,cmp);
	for(int i=1;i<=q;i++){
		int L=t[i].l;	int R=t[i].r;
		while(cl<L)	del(cl++);
		while(cl>L)	add(--cl);
		while(cr<R)	add(++cr);
		while(cr>R)	del(cr--);
		res[t[i].id]=(cnt==R-L+1);
	}
	for(int i=1;i<=q;i++)	puts(res[i]?"Yes":"No");
	return 0;
}