Luogu

分析

考虑莫队，并开两个 bitset，分别存 $x$ 是否在区间内和 $100000-x$ 是否在区间内，假设分别叫 $A$ 和 $B$。

那么对于询问 $-$，直接判断 A&(A<<x) 是否有 $1$ 即可；对于询问 $+$，直接判断 B&(A<<(100000-x)) 是否有 $1$ 即可。这两种询问单次都是 $\mathcal{O}(\frac{n}{\omega})$ 的。

对于询问 $\times$，直接枚举 $x$ 的约数 $d$ 并判断 $d$ 和 $\frac{x}{d}$ 是否都存在即可，单次询问 $\mathcal{O}(\sqrt{n})$。

对于询问 $\div$，一个想法是直接枚举 $d$ 并判断 $d$ 和 $dx$ 是否都存在。然而这个只有在 $x\geq\sqrt{n}$ 时单次询问的复杂度才是 $\mathcal{O}(\sqrt{n})$。

因此我们把所有 $x<\sqrt{n}$ 的询问 $\div$ 单独拿出来求：枚举 $x\in[1,\sqrt{n})$，然后从左往右枚举右端点 $r$，并求出 $lst_t$ 表示 $t$ 上一次出现的位置和 $mx_r$ 表示最大的满足 $[l,r]$ 内能有两个数商为 $x$ 的 $l$（直接用 $lst$ 更新即可），这样子只需要对于右端点是 $r$ 的询问判断它的左端点是否 $\leq mx_r$ 即可。这一部分总复杂度是 $\mathcal{O}(n\sqrt{n})$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
using namespace std;
typedef long long ll;

namespace IO {
    const int SIZE=1<<21;
    char ibuf[SIZE|1],*iS=ibuf,*iT=ibuf,obuf[SIZE|1],*oS=obuf,*oT=obuf+SIZE-1;
    void flush() { fwrite(obuf,1,oS-obuf,stdout); oS=obuf; }
    char getc() {
        if (iS==iT) {
            iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin);
            if (iS==iT) return EOF;
        }
        return *iS++;
    }
    void putc(char x) { *oS++=x; if (oS==oT) flush(); }
    int read() {
        int X=0,w=1; char c=getc();
        while (c<'0'||c>'9') { if (c=='-') w=-1; c=getc(); }
        while (c>='0'&&c<='9') X=X*10+c-'0',c=getc();
        return X*w;
    }
    struct flusher { ~flusher() { flush(); } } io_flusher;
}
using IO::putc;
using IO::read;

const int N=100000+10;

int n,m,Q=0,a[N],B;
bool ans[N];
struct query { int op,l,r,x,id; } q[N];
bool operator <(query a,query b) {
    if (a.l/B!=b.l/B) return a.l<b.l;
    else return (a.l/B)&1?a.r<b.r:a.r>b.r;
}
vector<query> q2[N];

namespace SP {
    int lst[N],mx[N];
    void main() {
        for (int w=1;w<=316;++w) {
            memset(lst,0,sizeof(lst)),memset(mx,0,sizeof(mx));
            if (q2[w].empty()) continue;
            for (int i=1,p=0;i<=n;++i) {
                lst[a[i]]=i;
                if (w*a[i]<=100000) p=max(p,lst[w*a[i]]);
                if (a[i]%w==0) p=max(p,lst[a[i]/w]);
                mx[i]=p;
            }
            for (auto i:q2[w]) ans[i.id]=(i.l<=mx[i.r]);
        }
    }
}

bitset<N> B1,B2; int cnt[N];
void add(int x) {
    if (!cnt[x]) B1[x]=B2[100000-x]=1;
    ++cnt[x];
}
void del(int x) {
    --cnt[x];
    if (!cnt[x]) B1[x]=B2[100000-x]=0;
}

bool Q1(int x) { // -
    return (B1&(B1<<x)).any();
}
bool Q2(int x) { // +
    return (B2&(B1<<(100000-x))).any();
}
bool Q3(int x) { // *
    for (int i=1;i*i<=x;++i)
        if (x%i==0&&B1[i]&&B1[x/i]) return 1;
    return 0;
}
bool Q4(int x) { // /
    for (int i=1;i*x<=100000;++i)
        if (B1[i]&&B1[i*x]) return 1;
    return 0;
}

int main() {
    n=read(),m=read(); B=sqrt(n);
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=m;++i) {
        int op=read(),l=read(),r=read(),x=read();
        if (op==4&&x<=316) q2[x].emplace_back((query){op,l,r,x,i});
        else q[++Q]=(query){op,l,r,x,i};
    }
    SP::main(); sort(q+1,q+Q+1);
    for (int i=1,l=1,r=0;i<=Q;++i) {
        while (l>q[i].l) --l,add(a[l]);
        while (r<q[i].r) ++r,add(a[r]);
        while (l<q[i].l) del(a[l]),++l;
        while (r>q[i].r) del(a[r]),--r;
        if (q[i].op==1) ans[q[i].id]=Q1(q[i].x);
        if (q[i].op==2) ans[q[i].id]=Q2(q[i].x);
        if (q[i].op==3) ans[q[i].id]=Q3(q[i].x);
        if (q[i].op==4) ans[q[i].id]=Q4(q[i].x);
    }
    for (int i=1;i<=m;++i) {
        if (ans[i]) putc('y'),putc('u'),putc('n'),putc('o');
        else putc('y'),putc('u'),putc('m'),putc('i');
        putc('\n');
    }
    return 0;
}