发布时间：2025-05-22

查询区间两个数$+,-,*,/$等于x

维护一个bitset，第$i$位表示是否出现$i$，以及一个反bitset，第$N-i$位表示出现$i$

• $a-b=x$,$b=a-x$,答案就是now&(now>>x).any()
• $a+b=x,N-a=a',N-a'+b=x,b=a'-(N-x)$，答案就是now&(rev>>N-x).any()
• $a*b=x$,暴力质因数分解$x$，判断
• $a/b=x$ * 如果$x > \sqrt N$，那么$i*x$的$i$小于等于$\sqrt N$，暴力枚举判断 * 否则预处理$\leq \sqrt N$的答案，$mxl_{x,i}$表示到$i$位置，存在$x，ix$的最大左端点，判断$l \leq mxl_{x,r}$即可

const int N=1e5+10;
bitset<N> now,rev;
void solve(){
    int n,q;
    cin>>n>>q;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    init(n);
    vector<int> lst(N),cnt(N);
    int sq=sqrt(N);
    vector mxl(sq+1,vector<int>(n+1,-1));
    for(int i=1;i<=n;i++){
        lst[a[i]]=i;
        for(int x=1;x<=sq;x++){// 预处理
            mxl[x][i]=mxl[x][i-1];
            if(a[i]*x<N&&lst[a[i]*x])mxl[x][i]=max(mxl[x][i],lst[a[i]*x]);
            if(a[i]%x==0&&lst[a[i]/x])mxl[x][i]=max(mxl[x][i],lst[a[i]/x]);
        }
    }
    vector<bool> ans(q);
    for(int i=0;i<q;i++){
        int op,l,r,x;
        cin>>op>>l>>r>>x;
        que.push_back({i,op,l,r,x});
    }
    sort(que.begin(),que.end(),cmp);
    auto add=[&](int x){
        if(!cnt[a[x]]){
            now.set(a[x]);
            rev.set(N-a[x]);
        }
        cnt[a[x]]++;
    };
    auto del=[&](int x){
        cnt[a[x]]--;
        if(!cnt[a[x]]){
            now.reset(a[x]);
            rev.reset(N-a[x]);
        }
    };  
    int l=1,r=0;
    for(auto &[id,op,ql,qr,x]:que){
        while(r<qr)add(++r);
        while(l>ql)add(--l);
        while(r>qr)del(r--);
        while(l<ql)del(l++);
        if(op==1){
            ans[id]=(now&(now<<x)).any();
        }
        else if(op==2){
            ans[id]=(now&(rev>>(N-x))).any();
        }
        else if(op==3){
            for(int i=1;i*i<=x;i++){
                if(x%i==0&&cnt[i]&&cnt[x/i]){
                    ans[id]=1;
                    break;
                }
            }
        }
        else{
            if(x==0)ans[id]=0;
            else if(x<=sq)ans[id]=(ql<=mxl[x][qr]);
            else{
                for(int i=1;i*x<N;i++){
                    if(cnt[i]&&cnt[i*x]){
                        ans[id]=1;
                        break;
                    }
                }
            }
        }
    }
    for(int i=0;i<q;i++){
        if(ans[i])cout<<"yuno\n";
        else cout<<"yumi\n";
    }
}