luogu_P3674 小清新人渣的本愿

传送门

Solution

莫队，用bitset来存储出现的数

如果是和或者差，直接通过左移右移就可以实现判断

对于积的询问，暴力判就行了，因数只要枚举\(\sqrt n\)个

总复杂度是\(O(n^2/32)\)，反正\(3s\)是可以过的咯

Code

#include<bits/stdc++.h>

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

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;

}

#define MN 100005

#define N MN

int n,m,a[MN],T;

bool Ans[MN];

std::bitset<N> now,fnow;

struct ques{

    int l,r,opt,x,id,pl;

    bool operator <(const ques&o)const{return (pl^o.pl)?(pl<o.pl):(r<o.r);}

}q[MN];

int num[MN];

int main()

{

    //freopen("testdata.in","r",stdin);

    //freopen("testdata.out","w",stdout);

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

    register int i;T=ceil(sqrt((double)n));

    for(i=1;i<=n;++i) a[i]=read();

    now.reset();fnow.reset();

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

    {

        q[i].opt=read(),q[i].l=read(),q[i].r=read();

        q[i].x=read(),q[i].pl=(q[i].l-1)/T+1;q[i].id=i;

    }

    std::sort(q+1,q+m+1);

    register int l=1,r=0,j;

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

    {

        //printf("l=%d r=%d\n",q[i].l,q[i].r);

        for(;r<q[i].r;++r) if(!num[a[r+1]]++) now[a[r+1]]=1,fnow[N-a[r+1]]=1;

        for(;l>q[i].l;--l) if(!num[a[l-1]]++) now[a[l-1]]=1,fnow[N-a[l-1]]=1;

        for(;r>q[i].r;--r) if(!(--num[a[r]])) now[a[r]]=0,fnow[N-a[r]]=0;

        for(;l<q[i].l;++l) if(!(--num[a[l]])) now[a[l]]=0,fnow[N-a[l]]=0;

        //std::cout<<now<<std::endl<<fnow<<std::endl;

        if(q[i].opt==1) Ans[q[i].id]=(now&(now<<q[i].x)).any();

        else if(q[i].opt==2) Ans[q[i].id]=((now<<(N-q[i].x))&fnow).any();

        else

        {

            for(j=1;j*j<=q[i].x;j++)

                if(q[i].x%j==0) if(now[j]&&now[q[i].x/j]){Ans[q[i].id]=1;break;}

        }

    }

    for(i=1;i<=m;++i) puts(Ans[i]?"hana":"bi");

    return 0;

}

Blog来自PaperCloud，未经允许，请勿转载，TKS！

巴特西

luogu_P3674 小清新人渣的本愿

传送门

Solution

Code

最新文章

热门文章