现有数列A1,A2,?,ANA_1,A_2,\cdots,A_NA1?,A2?,?,AN?，Q 个询问(Li,Ri)(L_i,R_i)(Li?,Ri?)，ALi,ALi+1,?,ARiA_{Li} ,A_{Li+1},\cdots,A_{Ri}ALi?,ALi+1?,?,ARi? 是否互不相同
第1 行，2 个整数N,QN,QN,Q
第2 行，N 个整数ALi,ALi+1,?,ARiA_{Li} ,A_{Li+1},\cdots,A_{Ri}ALi?,ALi+1?,?,ARi?
Q 行，每行2 个整数Li,RiL_i,R_iLi?,Ri?
输出格式：对每个询问输出一行，“Yes” 或者“No”
• 对于50% 的数据，N,Q≤103N,Q \le 10^3N,Q≤103
• 对于100% 的数据，1≤N,Q≤105,1≤Ai≤N,1≤Li≤Ri≤N1 \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
【解题思路】
奇偶性排序
15 inline bool cmp(Node a,Node b){
16 return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r)；
17 }
莫队是一个很神奇的算法
主要的变化在ADD 和REMOVE函数中
对于出现过的数直接记录下来，answer记录出现了多少个不同的数，如果answer等于现在的R-L+1，那么说明出现的数与L到R相同。
【code】
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 #include <iostream> 5 using namespace std; 6 int a[100005],cnt[100005]; 7 int n,m,curL,curR,ans; 8 int block; 9 struct Node{ 10 int l; 11 int r; 12 int id; 13 }q[100005]; 14 bool ok[100005]; 15 inline bool cmp(Node a,Node b){ 16 return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r); 17 } 18 19 inline void add(int pos){ 20 cnt[a[pos]]++; 21 if(cnt[a[pos]]==1)ans++; 22 } 23 inline void remove(int pos){ 24 cnt[a[pos]]--; 25 if(cnt[a[pos]]==0)ans--; 26 } 27 int main(){ 28 scanf("%d%d",&n,&m); 29 for(register int i=1;i<=n;i++) 30 scanf("%d",&a[i]); 31 block=sqrt(n)*1.0; 32 for(register int i=1;i<=m;i++){ 33 scanf("%d%d",&q[i].l,&q[i].r); 34 q[i].id=i; 35 } 36 sort(q+1,q+m+1,cmp); 37 for(register int i=1;i<=m;i++){ 38 while(curL>q[i].l)add(--curL); 39 while(curR<q[i].r)add(++curR); 40 while(curL<q[i].l)remove(curL++); 41 while(curR>q[i].r)remove(curR--); 42 if(ans==(q[i].r-q[i].l+1)) 43 ok[q[i].id]=1; 44 } 45 for(register int i=1;i<=m;i++) 46 if(ok[i]==1){ 47 printf("Yes\n"); 48 } 49 else printf("No\n"); 50 return 0; 51 }
原文：https://www.cnblogs.com/66dzb/p/11233650.html