现有数列 A_1,A_2,\cdots,A_NA1?,A2?,?,AN? ，Q 个询问 (L_i,R_i)(Li?,Ri?) ， A_{Li} ,A_{Li+1},\cdots,A_{Ri}ALi?,ALi+1?,?,ARi? 是否互不相同
输入格式：
第1 行，2 个整数 N,QN,Q
第2 行，N 个整数 A_{Li} ,A_{Li+1},\cdots,A_{Ri}ALi?,ALi+1?,?,ARi?
Q 行，每行2 个整数 L_i,R_iLi?,Ri?
输出格式：
对每个询问输出一行，“Yes” 或者“No”
• 对于50% 的数据， N,Q \le 10^3N,Q≤103
• 对于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≤105,1≤Ai?≤N,1≤Li?≤Ri?≤N
分析：很明显的莫队模板，轻松A。不过过程中被卡了读优。。。有点尴尬。。。
Code：
1 #include<bits/stdc++.h> 2 #define Fi(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 const int N=1e5+7; 5 int n,m,s,num=0,d[N],pos[N],sum[N];bool ans[N]; 6 struct Node{int l,r,id;}a[N]; 7 inline bool cmp(Node x,Node y) 8 {return pos[x.l]==pos[y.l]?x.r<y.r:x.l<y.l;} 9 inline void change(int i,bool f) 10 { 11 if(f){sum[d[i]]++;if(sum[d[i]]==1)num++;} 12 else {sum[d[i]]--;if(sum[d[i]]==0)num--;} 13 } 14 int main() 15 { 16 ios::sync_with_stdio(false); 17 cin>>n>>m;s=int(sqrt(n)); 18 memset(ans,false,sizeof(ans)); 19 Fi(i,1,n){cin>>d[i];pos[i]=(i-1)/s+1;} 20 Fi(i,1,m){cin>>a[i].l>>a[i].r;a[i].id=i;} 21 sort(a+1,a+1+m,cmp);int l=1,r=0; 22 Fi(i,1,m){ 23 while(l<a[i].l)change(l++,0); 24 while(l>a[i].l)change(--l,1); 25 while(r<a[i].r)change(++r,1); 26 while(r>a[i].r)change(r--,0); 27 if(num==a[i].r-a[i].l+1)ans[a[i].id]=true;} 28 Fi(i,1,m)if(ans[i])printf("Yes\n");else printf("No\n"); 29 return 0; 30 }
原文：https://www.cnblogs.com/cytus/p/9082565.html