P5355 由乃的玉米田

题面

原题链接 click

题解

考虑莫队配合 bitset，可以处理加减。
乘法直接枚举因数，容易处理。
除法的话，如果商较大（\(>k\)），可以直接枚举。
如果商很小，直接枚举每种可能的商，然后分别跑莫队配合 bitset 即可。
取 \(k\sim w\)，可以得到 \(O(\frac{n^2}{w}+n\sqrt{nw})\) 的复杂度，可以通过。

Code

#include<bits/stdc++.h>
using namespace std;
const int lim=24;
bitset<100005>x,y;
int tx[100005];
int a[100005];
int n,q;
struct qry{
    int id,op,v,l,r,ans;
};
qry s[100005];
bool cmp1(qry x,qry y){
    if(x.l/300!=y.l/300) return x.l<y.l;
    if((x.l/300)%2==0) return x.r<y.r;
    return x.r>y.r;
}
bool cmp2(qry x,qry y){
    if(x.l/1500!=y.l/1500) return x.l<y.l;
    if((x.l/1500)%2==0) return x.r<y.r;
    return x.r>y.r;
}
bool cmp3(qry x,qry y){
    return x.id<y.id;
}
inline void add1(int u){
    x[u]=1; y[100000-u]=1; tx[u]++;
}
inline void del1(int u){
    tx[u]--; if(!tx[u]){
        x[u]=0; y[100000-u]=0;
    }
}
bool chk1(int v){
    return !(x&(x<<v)).none();
}
bool chk2(int v){
    return !(x&(y>>(100000-v))).none();
}
bool chk3(int v){
    for(int i=1;i*i<=v;i++){
        if(v%i==0&&x[i]&&x[v/i]){
            return 1;
        }
    }return 0;
}
bool chk4(int v){
    for(int i=1;i*v<=100000;i++){
        if(x[i]&&x[i*v]) return 1;
    }return 0;
}
inline int add2(int v,int c){
    int res=0;
    if(!tx[v]){
        if(v*c<=100000) res+=bool(tx[v*c]);
        if(v%c==0) res+=bool(tx[v/c]);
    }
    tx[v]++;
    return res;
}
inline int del2(int v,int c){
    int res=0;
    tx[v]--;
    if(!tx[v]){
        if(v*c<=100000) res+=bool(tx[v*c]);
        if(v%c==0) res+=bool(tx[v/c]);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=q;i++){
        s[i].id=i; cin>>s[i].op>>s[i].l>>s[i].r>>s[i].v;
    }
    sort(s+1,s+1+q,cmp1);
    int nl=1,nr=0;
    for(int i=1;i<=q;i++){
        if(s[i].op==4&&s[i].v<=lim){
            if(s[i].v==1) s[i].ans=1;
            continue;
        }
        while(nl>s[i].l) add1(a[--nl]);
        while(nr<s[i].r) add1(a[++nr]);
        while(nl<s[i].l) del1(a[nl++]);
        while(nr>s[i].r) del1(a[nr--]);
        if(s[i].op==1) s[i].ans=chk1(s[i].v);
        if(s[i].op==2) s[i].ans=chk2(s[i].v);
        if(s[i].op==3) s[i].ans=chk3(s[i].v);
        if(s[i].op==4) s[i].ans=chk4(s[i].v);
    }
    sort(s+1,s+1+q,cmp2);
    for(int c=2;c<=lim;c++){
        memset(tx,0,sizeof(tx));
        int nl=1,nr=0,nw=0;
        for(int i=1;i<=q;i++){
            if(s[i].op==4&&s[i].v==c){
                while(nl>s[i].l) nw+=add2(a[--nl],c);
                while(nr<s[i].r) nw+=add2(a[++nr],c);
                while(nl<s[i].l) nw-=del2(a[nl++],c);
                while(nr>s[i].r) nw-=del2(a[nr--],c);
                s[i].ans=bool(nw);
            }
        }
    }
    sort(s+1,s+1+q,cmp3);
    for(int i=1;i<=q;i++){
        cout<<(s[i].ans?"yuno":"yumi")<<'\n';
    }
    return 0;
}