Steven_MengのBlog

传送门

设现在莫队指针$l,r$维护的区间中不同的数组成的集合为${a_1,a_2,a_3…a_n}$

我们维护这样一个$\rm bitset$$s$,对于$a_i$,$s[a_i]=1$

Query1

考虑如何实现查询$x-y=n$,发现$x=y+n$,所以对于所有出现在$a$集合中的数$a_i$,查询$a_i+n$在$a$集合中有没有出现即可。

这个可以通过操作$(s \text{&} (s<<n)).any()$实现,其中$any()$查询$\rm bitset$中有没有$1$

Query2

考虑实现查询$x+y=n$,其实本质和上面一种一样,就是化成$x=-y+n$,再维护一个下标为$-a_i$的$\rm bitset$$s1$即可,但是这样做会有一个严重的问题,$\rm bitset$下标不能为负数。

考虑给$-a_i$加上一个很大的正数$N$,这里使用$MAXN-1$

把$s1$维护的数变为集合$b_i=-a_i+N$,原来的式子化成$x=-y+N+n-N$

查询的操作转换成查询$b_i+n-N$有没有在$a_i$中出现。

注意到$n-N$为负数,于是左移$n-N$转换成右移$N-n$。

通过操作$(s \text{&} (s1>>(N-n))).any()$实现。

Query3

这个比较简单,将$xy=n$转换成$x=\frac{n\dfrac,于是$O(\sqrt{n})$枚举$n$的所有因数即可。

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
// luogu-judger-enable-o2
//小清新莫队题
#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<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
bitset<MAXN>s,s1;
int a[MAXN],cnt[MAXN],pos[MAXN];
// #define Add(x) if (cnt[x]++==0) s[x]=1,s1[MAXN-1-x]=1
// #define Del(x) if (--cnt[x]==0) s[x]=0,s1[MAXN-1-x]=0
inline void Add(int x){
if (cnt[x]++==0) s[x]=1,s1[MAXN-1-x]=1;
}
inline void Del(int x){
if (--cnt[x]==0) s[x]=0,s1[MAXN-1-x]=0;
}
struct Query{
int opt,l,r,x,id;
}q[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 ans[MAXN];
int main(){
int n=read(),m=read();
int Size=(int)(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){
int opt=read(),l=read(),r=read(),x=read();
q[i]=Query{opt,l,r,x,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) Del(a[l++]);
while (l>q[i].l) Add(a[--l]);
while (r>q[i].r) Del(a[r--]);
while (r<q[i].r) Add(a[++r]);
if (q[i].opt==1){
ans[q[i].id]=(s&(s<<(q[i].x))).any();
}
else if (q[i].opt==2){
ans[q[i].id]=(s&(s1>>(MAXN-1-q[i].x))).any();
}
else if (q[i].opt==3){
for (register int j=1;j*j<=q[i].x;++j){
if (q[i].x%j!=0) continue;
if (s[j]&&s[q[i].x/j]){
ans[q[i].id]=1;
break;
}
}
}
}
for (register int i=1;i<=m;++i){
puts(ans[i]==1?"hana":"bi");
}
}

最后提一点需要特别注意,不能乱用$\rm define$,比如说

1
#define Add(x) if (cnt[a[x]]) s[a[x]]=true;

调用时

1
Add(l++)

其实相当于

1
if (cnt[a[l++]]) s[a[l++]]=true

会导致$\rm WA$

 评论