Steven_MengのBlog

传送门

莫队是一种多么优美的算法,肿么能不用莫队呢?

只要记录区间出现次数超过$2$的数就可以搞定了(代码中是$cnt2$)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Query{
int l,r,id;
}q[MAXN];
int pos[MAXN];
inline bool operator < (const Query &a,const Query &b){
return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));
}
int a[MAXN],cnt[MAXN],cnt2;
inline void Add(int x){
++cnt[x];
if (cnt[x]==2) cnt2++;
}
inline void Del(int x){
--cnt[x];
if (cnt[x]==1) cnt2--;
}
int Ans[MAXN];
int main(){
int n=read(),m=read();
int Size=sqrt(n);
for (register int i=1;i<=n;++i){
a[i]=read();
pos[i]=(i-1)/Size+1;
}
for (register int i=1;i<=m;++i){
q[i]=Query{read(),read(),i};
}
sort(q+1,q+1+m);
int l=1,r=0;
for (register int i=1;i<=m;++i){
while (l>q[i].l) Add(a[--l]);
while (r<q[i].r) Add(a[++r]);
while (r>q[i].r) Del(a[r--]);
while (l<q[i].l) Del(a[l++]);
Ans[q[i].id]=(cnt2==0);
}
for (register int i=1;i<=m;++i){
puts(Ans[i]?"Yes":"No");
}
}

 评论