我不知道题解应该叫什么名字

· · 题解

设 n,m,K 同阶，其中 K 是值域大小。

尝试直接维护能否得到某个值。

但是这样更新的时候一定需要得到现在有什么，才能够加以处理，这还不如暴力。

因此，转而去维护当前有什么值，再尝试通过这些值去检查当前答案是否合法。

我们先维护一个 bitset 存储当前区间有哪些数。

对于寻找 a-b=x，我们将当前这个 bitset 右移 x 位，那么，原本的 a 就会移动到 a-x 的位置。

而 a+b=x，则 a-x=b。

因此，如果有合法的解，我们将这两个 bitset 取交集一定非空。

bitset 的 any 函数可以检验是否有 1，所以判断一下 (now1&(now1>>x)).any() 即可。

类似的，a+b=x，则 b=x-a。

但是 x-a 并不好维护。

所以我们维护另外一个 bitset，若第 i 位为 1，则 K-i 这个数是存在的。

那么，如果原本的 x-a 在 now1 中存在，其就会在 now2 中在 K-x+a 的位置存在。

我们要将其对齐到 b 位置。

因此，这个 x-a 就被转化为了第二个 bitset 右移 K-x 位的产物。

那么，我们就可以判断 (now1&(now2>>(K-x))).any() 了。

直接用 bitset 做是困难的，但是我们可以直接枚举因数，显然这个 O(\sqrt n) 的。

我们已经证明了前面的时间复杂度是 O(\frac {n^2}{w}+n \sqrt n) 的了，因为除法不太一样，我们拉出来单独讲。

那么就是要处理 \frac a b=x，则 a=b \times x。

那么我们需要去找对应的 a,b。

一个直接的思路是去大力枚举当前的 b，但是这个时间复杂度是 O(\frac n x) 的，总时间复杂度就是 O(\frac{n^2}{x})。

看到这个时间复杂度，我们发现这很像根号分治。

尝试去找到另外一个时间复杂度为 O(nx) 的做法。

我们去枚举当前的每一个 x，找到对于当前的 x 下，每一个数 i 的左侧的第一个倍数和第一个约数的位置的更偏右的值 pre。

那么，如果当前区间中同时存在 i 和 x，这就是合法的。

那么，我们要检查的就是，当前询问区间的 pre 的最大值在不在区间内。

发现这个 pre 是可以和前一个取 max 的。

因为 pre_x \le x，如果我们包含 pre_x，x 一定也在这之内。

所以和前一个取 max 之后，我们只需要判断 pre_r 是否在当前区间内。

容易证明这个做法的时间复杂度是 O(nx) 的。

于是，我们进行一个根号分治，取 x=\sqrt n，可以将时间复杂度平衡到 O(n \sqrt n)。

:::success[代码]

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5,B=350,K=1e5;
struct edge{int op,l,r,x,id;}b[N];
vector<int> v[B+5];int pre[N],last[N];//根号分治 
int a[N],tmp[N],belong[N];bitset<N> now1,now2;bool ans[N];

inline int read(){
    int s=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*f;
}

inline bool operator < (edge x,edge y){
    if(belong[x.l]!=belong[y.l]) return belong[x.l]<belong[y.l];
    return (belong[x.l]&1)?(x.r<y.r):(x.r>y.r);
}

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

inline void del(int x){
    tmp[x]--;
    if(tmp[x]==0) now1[x]=now2[K-x]=0;
}

int main(){
//  freopen("hack.txt","r",stdin);
//  freopen("hack.out","w",stdout);
    int n,m;cin>>n>>m;int block=(int)sqrt(n);
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=m;i++) b[i]={read(),read(),read(),read(),i};
    for(int i=1;i<=n;i++) belong[i]=i/block;
    sort(b+1,b+m+1);int l=1,r=0;
    for(int i=1;i<=m;i++){
        if(b[i].op==4 && b[i].x<=B){v[b[i].x].push_back(i);continue;} //根号分治处理除法
        while(l>b[i].l) l--,add(a[l]);
        while(r<b[i].r) r++,add(a[r]);
        while(l<b[i].l) del(a[l]),l++;
        while(r>b[i].r) del(a[r]),r--;
        int x=b[i].x;
        if(b[i].op==1){
            ans[b[i].id]=(now1&(now1>>x)).any();
        }else if(b[i].op==2){
            ans[b[i].id]=(now1&(now2>>(K-x))).any();
        }else if(b[i].op==3){//乘法，枚举约数 
            int tm=(int)sqrt(x);
            for(int j=1;j<=tm;j++)
                if(x%j==0 && now1[j] && now1[x/j]) ans[b[i].id]=1;
        }else{//除法，保证 x>B，暴力寻找 
            for(int j=1;j*x<=K;j++)  
                if(now1[j] && now1[j*x]) ans[b[i].id]=1;
        }
    }
    for(int tx=1;tx<=B;tx++){//对除法进行根号分治，注意不要枚举 x，一定不合法，且我们有 a[i]/tx，枚举 0 会炸 
        if(v[tx].size()==0) continue;//没有当前这个
        //得到当前的 pre 数组
        for(int i=1;i<=n;i++){
            last[a[i]]=i;pre[i]=pre[i-1];
            if(a[i]%tx==0) pre[i]=max(pre[i],last[a[i]/tx]);
            if(a[i]*tx<=K) pre[i]=max(pre[i],last[a[i]*tx]);
        }
        //求当前查询是否合法
        for(int now=0;now<v[tx].size();now++){
            int i=v[tx][now];//当前查询在排序后的编号
            ans[b[i].id]=(b[i].l<=pre[b[i].r]);//在当前区间内就合法 
        }
        for(int i=1;i<=K;i++) last[i]=0;//清空 
    }
    for(int i=1;i<=m;i++) cout<<(ans[i]?"yuno":"yumi")<<"\n";
    return 0;
}

:::