洛谷 P3901 数列找不同（莫队）

题目链接：https://www.luogu.com.cn/problem/P3901

这道题简单莫队模板题，然后$add$和$del$分别处理$vis[]$从$0-->1$和从$1-->0$的情况，用一个$ans$记录，

最后如果$ans==(R-L+1)$，那么就说明并没有重复的，反之。

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 typedef long long ll;
 8 const int N=100005;
 9 int ans,block;
10 int a[N],vis[N],tot[N];
11 
12 struct node{
13     int l,r;
14     int id;
15 }q[N];
16 
17 bool cmp(node aa,node bb){
18     if(aa.l/block==bb.l/block) return aa.r<bb.r;
19     return aa.l/block<bb.l/block;
20 }
21 
22 void add(int pos){
23     vis[a[pos]]++;
24     if(vis[a[pos]]==1) ans++;
25 }
26 
27 void del(int pos){
28     vis[a[pos]]--;
29     if(vis[a[pos]]==0) ans--;
30 }
31 
32 int main(){
33     int n,m;
34     scanf("%d%d",&n,&m);
35     block=sqrt(n);
36     for(int i=1;i<=n;i++) scanf("%d",&a[i]);
37     for(int i=1;i<=m;i++){
38         scanf("%d%d",&q[i].l,&q[i].r);
39         q[i].id=i;
40     }
41     sort(q+1,q+m+1,cmp);
42     int L=1,R=0;
43     for(int i=1;i<=m;i++){
44         while(L<q[i].l){
45             del(L);
46             L++;
47         }
48         while(L>q[i].l){
49             L--;
50             add(L);
51         }
52         while(R<q[i].r){
53             R++;
54             add(R);
55         }
56         while(R>q[i].r){
57             del(R);
58             R--;
59         }
60         if(ans==q[i].r-q[i].l+1) tot[q[i].id]=1;
61     }
62     for(int i=1;i<=m;i++){
63         if(!tot[i]) printf("No
");
64         else printf("Yes
");
65     }
66     return 0;
67 }

AC代码