【bzoj4810】由乃的玉米田

lxl丧心病狂……

首先允许离线的区间询问一看就是莫队。那么我们看下怎么莫队？

不会。

“由乃题多半是不可做的。”于是我看了下题解……好吧果然是bitset

用bitset维护当前出现了哪些数。对于差为x，可以将其左移然后和本身取并集，和为x，我们可以翻转这个bitset，然后左移取并集就好了。对于乘积为x，我们可以暴力，枚举因数判断一下就好了。

还好这个时候的lxl还没有热衷卡常……

#include<bits/stdc++.h>

#define N 100000

#define M 20000005

using namespace std;

struct Query{int k,l,r,x,id;}q[N+5];

int m,n,l,r,s;

int a[N+5],c[N+5],ans[N+5],rt[N+5];

bitset<N+5> now1,now2;

char DR[M+10],*P=DR;

inline bool operator<(Query x,Query y){

    return rt[x.l]==rt[y.l]?rt[x.l]&1?x.r<y.r:x.r>y.r:rt[x.l]<rt[y.l];

}

int read(){

    int f=1,x=0;char ch;

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

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

    return f*x;

}

inline void init(){

    n=read();m=read();s=(int)sqrt(n);

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

    for(register int i=1;i<=n;++i)rt[i]=(i-1)/s+1;

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

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

        q[i].x=read();q[i].id=i;

    }

    sort(q+1,q+m+1);l=1;r=0;

}

inline void add(int x){if(c[x]++==0)now1[x]=1,now2[N-x]=1;}

inline void del(int x){if(--c[x]==0)now1[x]=0,now2[N-x]=0;}

int main(){

    init();

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

        for(;q[i].l<l;)add(a[--l]);

        for(;q[i].l>l;)del(a[l++]);

        for(;q[i].r<r;)del(a[r--]);

        for(;q[i].r>r;)add(a[++r]);int k=q[i].k,x=q[i].x;

        if(k==1){if((now1&(now1<<x)).any())ans[q[i].id]=1;}

        else if(k==2){if((now1&(now2>>(N-x))).any())ans[q[i].id]=1;}

        else{

            for(int j=1;j*j<=x;j++)

                if(!(x%j))if(now1[j]&&now1[x/j]){ans[q[i].id]=1;break;}

        }

    }

    for (int i=1;i<=m;i++)if(ans[i])puts("yuno");else puts("yumi");

    return 0;

}