题目描述

现有数列A1,A2,⋯,A N，Q 个询问(L i,R i)，ALi,ALi+1,⋯,ARi 是否互不相同

输入格式

第1 行，2 个整数N,Q

第2 行，N 个整数ALi,ALi+1,⋯,A R i

Q 行，每行2 个整数L i,R i

输出格式

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

---

怎么判区间内的数是否互不相同呢？

设区间长度为len，互不相同可以看成是区间内有len个不同的数。那么我们统计就好了。

暴力一点，统计用莫队

时间复杂度为O(N√N)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define maxn 100001using namespace std;int n,m,val[maxn];bool ans[maxn];inline int read(){    register int x(0),f(1); register char c(getchar());    while(c<'0'||'9'
         
          q[i].l) add(--l); while(r
          
           q[i].r) del(r--); ans[q[i].id]=(tot==q[i].r-q[i].l+1); }}int main(){ n=read(),m=read(),unit=sqrt(n); for(register int i=1;i<=n;i++) val[i]=read(); for(register int i=1;i<=m;i++) q[i].l=read(),q[i].r=read(),q[i].id=i,q[i].col=q[i].l/unit+1; solve(); for(register int i=1;i<=m;i++) printf("%s\n",ans[i]?"Yes":"No"); return 0;}