luogu P3674 小清新人渣的本愿（莫队+bitset)

这题是莫队维护bitset。

然而我并不会bitset以前讲过认为不考就没学

我真的太菜了。

首先维护一个权值的bitset——s。

操作3比较简单，我们可以\(\sqrt{x}\)枚举约数然后判断就行了。

操作1就是求是否存在

\[\exists{a,b},a-b=x
\]

移一下项

\[a=x+b
\]

也就是\(\text{(s<<x)}\)&\(x\neq0\)。

那么操作2该怎么办?

我们先设\(b'=n-b\)因为\(x=a+b\)

\[a-b'=a-(n-b)=a+b-n=x-n
\]

然后类比操作1就行了。

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<bitset>

using namespace std;

const int N=100101;

int n,m,a[N],block[N],cnt[N];

string ans[N];

struct ques{

    int l,r,type,id,x;

}qu[N];

bool cmp(ques a,ques b){

    if(block[a.l]==block[b.l])return a.r<b.r;

    else return block[a.l]<block[b.l];

}

bitset<N> x,y;

int read(){

    int sum=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

    return sum*f;

}

int main(){

    n=read();m=read();

    int Block=sqrt(n);

    for(int i=1;i<=n;i++)a[i]=read(),block[i]=(i-1)/Block+1;

    for(int i=1;i<=m;i++)qu[i].type=read(),qu[i].l=read(),qu[i].r=read(),qu[i].x=read(),qu[i].id=i;

    sort(qu+1,qu+1+m,cmp);

    int l=1,r=0;

    for(int i=1;i<=m;i++){

        while(r<qu[i].r){

            r++;

            cnt[a[r]]++;

            if(cnt[a[r]]==1)x[a[r]]=1,y[n-a[r]]=1;

        }

        while(l>qu[i].l){

            l--;

            cnt[a[l]]++;

            if(cnt[a[l]]==1)x[a[l]]=1,y[n-a[l]]=1;

        }

        while(r>qu[i].r){

            if(cnt[a[r]]==1)x[a[r]]=0,y[n-a[r]]=0;

            cnt[a[r]]--;

            r--;

        }

        while(l<qu[i].l){

            if(cnt[a[l]]==1)x[a[l]]=0,y[n-a[l]]=0;

            cnt[a[l]]--;

            l++;

        }

        if(qu[i].type==1){

            if((x&(x<<qu[i].x)).any())ans[qu[i].id]="hana";

            else ans[qu[i].id]="bi";

        }

        else if(qu[i].type==2){

            if(qu[i].x-n>=0){

                if(((y<<(qu[i].x-n))&x).any())ans[qu[i].id]="hana";

                else ans[qu[i].id]="bi";

            }

            else{

                if(((x<<(n-qu[i].x))&y).any())ans[qu[i].id]="hana";

                else ans[qu[i].id]="bi";

            }

        }

        else{

            for(int j=1;j<=sqrt(qu[i].x);j++)

                if(qu[i].x%j==0&&x[j]&&x[qu[i].x/j])ans[qu[i].id]="hana";

            if(ans[qu[i].id]!="hana")ans[qu[i].id]="bi";

        }

    }

    for(int i=1;i<=m;i++)cout<<ans[i]<<endl;

    return 0;

}

巴特西

luogu P3674 小清新人渣的本愿（莫队+bitset)

最新文章

热门文章