Steven_Meng's 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}{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$，比如说

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

调用时

Add(l++)

其实相当于

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

会导致$\rm WA$