P3674 小清新人渣的本愿

传送门

设现在莫队指针 $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 & (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 & (s1>>(N-n))).any()实现。

Query3

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

// 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;

调用时

Add(l++)

其实相当于

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

会导致 $\rm WA$