题解 P3674 【小清新人渣的本愿】

· · 题解

因为值域比较小，我们又没有什么很好的方法去枚举（因为肯定超时），所以我们可以考虑用 bitset 去储存某个数是否出现。因为 bitset 的时间复杂度是 O(\dfrac{n}{w})（w 在 64 位系统上等于 64），所以 O(\dfrac{nm}{w}) 的时间复杂度在三秒之内一定能过。

现在加法就解决掉了。我们只需要开一个 bitset，

考虑做减法，我们突然发现一个 bitset 并不好从处理，于是准备另开一个 bitset 作为第一个 bitset 反串，相当于储存是否存在 n-x。现在我们的减法也处理完成了。

最后是乘法。我们直接暴力 O(\sqrt n) 进行处理，判断一下两个因子是否在区间出现过即可。

说了这么多，实际上我们还是没去想如何优秀地处理每个区间。实际上我们只需要用莫队去维护 bitset 即可。

#include<bits/stdc++.h>
using namespace std;
int pos[100005],a[100005],n,m,p,cnt[100005];
bool ans[100005];
struct queries{
    int op,l,r,x,id;
    queries(){op=l=r=x=id=0;}
    queries(int O,int L,int R,int X,int I){op=O,l=L,r=R,x=X,id=I;}
    bool operator < (queries qwq) const {
        if(pos[l]==pos[qwq.l])  return r<qwq.r;
        return l<qwq.l;
    }
}que[100005];
bitset<100005> pre,suf;
void add(int x)
{
    ++cnt[a[x]];
//    pre[a[x]]=1;
    pre.set(a[x]);
//    suf[n-a[x]]=1;
    suf.set(n-a[x]);
}
void sub(int x)
{
    --cnt[a[x]];
    if(!cnt[a[x]])
    {
        pre[a[x]]=0;
        suf[n-a[x]]=0;
    }
}
int main(){
    scanf("%d %d",&n,&m);
    p=sqrt(n);
    for(int i=1;i<=n;++i)   scanf("%d",&a[i]),pos[i]=(i-1)/p+1;
    for(int i=1;i<=m;++i)
    {
        int o,l,r,x,id=i;
        scanf("%d %d %d %d",&o,&l,&r,&x);
        que[i]=queries(o,l,r,x,id);
    }
    sort(que+1,que+1+m);
    for(int i=1,l=1,r=0;i<=m;++i)
    {
        while(l>que[i].l)   add(--l);
        while(l<que[i].l)   sub(l++);
        while(r<que[i].r)   add(++r);
        while(r>que[i].r)   sub(r--);
        if(que[i].op==1 && (pre&(pre<<que[i].x)).any()) ans[que[i].id]=true;
        if(que[i].op==2 && (pre&(suf>>(n-que[i].x))).any()) ans[que[i].id]=true;
        if(que[i].op==3)
        {
            for(int j=1;j*j<=que[i].x;++j)
            {
                if(que[i].x%j==0 && pre[j] && pre[que[i].x/j])
                {
                    ans[que[i].id]=true;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=m;++i)   puts(ans[i]?"hana":"bi");
    return 0;
}