数列找不同

题目描述
现有数列A_1,A_2,cdots,A_NA
1
​ ,A
2
​ ,⋯,A
N
​ ，Q 个询问(L_i,R_i)(L
i
​ ,R
i
​ )，A_{Li} ,A_{Li+1},cdots,A_{Ri}A
Li
​ ,A
Li+1
​ ,⋯,A
Ri
​ 是否互不相同

输入格式
第1 行，2 个整数N,QN,Q

第2 行，N 个整数A_{Li} ,A_{Li+1},cdots,A_{Ri}A
Li
​ ,A
Li+1
​ ,⋯,A
Ri
​

Q 行，每行2 个整数L_i,R_iL
i
​ ,R
i
​

输出格式
对每个询问输出一行，“Yes” 或者“No”

输入输出样例
输入 #1 复制
4 2
1 2 3 2
1 3
2 4
输出 #1 复制
Yes
No
说明/提示
• 对于50% 的数据，N,Q le 10^3N,Q≤10
3

• 对于100% 的数据，1 le N,Q le 10^5, 1 le A_i le N, 1 le L_i le R_i le N1≤N,Q≤10
5
,1≤A
i
​ ≤N,1≤L
i
​ ≤R
i
​ ≤N

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

const int maxn=100010;

inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
    	if(ch=='-'){
    		w=-1;
    	}
    	ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
    	s=s*10+ch-'0';
    	ch=getchar();
    }
    return s*w;
}

int n,m,hhh,ans=0,kkksc03,kkksc04,cnt[maxn],a[maxn],i;

bool anb[maxn];

struct node{
    int l,r,p;
}q[maxn];

bool cmp(const node x,const node y){
    return (x.l/hhh)==(y.l/hhh)?x.r<y.r:x.l<y.l;
}

void add(int position){
    if((++cnt[a[position]])==1){
		++ans;
	}
}

void remove(int position){
    if((--cnt[a[position]])==0){
		--ans;
	}
}

int main(){
	n=read();
	m=read();
	hhh=sqrt(n);
	for(i=1;i<=n;i++){
		a[i]=read();
	}
    for(i=1;i<=m;i++){
        q[i].l=read();
        q[i].r=read();
        q[i].p=i;
    }
    sort(q+1,q+1+m,cmp);
    for(i=1;i<=m;i++){
        int L=q[i].l,R=q[i].r;
        while(kkksc03<L){
			remove(kkksc03++);
		}
        while(kkksc03>L){
			add(--kkksc03);
		}
        while(kkksc04<R){
			add(++kkksc04);
		}
        while(kkksc04>R){
			remove(kkksc04--);
		}
        if(ans==(R-L+1)){
        	anb[q[i].p]=1;
        }
    }
    for(i=1;i<=m;i++){
        if(anb[i]==1){
        	printf("Yesn");
        }
        else{
        	printf("Non");
        }
    }
    return 0;
}

最后

以上就是饱满犀牛为你收集整理的数列找不同的全部内容，希望文章能够帮你解决数列找不同所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。