题目
P3674 小清新人渣的本愿的加强版，多了除操作。
分析
莫队+(bitset)+根号分治
对于前三个操作，请看这里。
这里只讨论除该怎么解决。
首先我们莫队无法很好地维护，于是考虑另外的思路。
我们可以考虑直接枚举一个数作为商，然后查看是否有被除数，但是这样做会因为 (x) 很小的时候复杂度很高。
于是考虑根号分治，对于 (sqrt{n}leq x) 的询问除，直接莫队，在询问的时候 (O(sqrt{n})) 回答即可。
对于 (xleq sqrt{n}) 的询问除，我们考虑单独维护：
因为这样的 (x) 不超过 (sqrt{n}) ，于是可以考虑枚举每一个 (x) 。
然后我们记 (las[i]) 表示值为 (i) 的最后出现的位置，(res[i]) 表示位置 (i) 在之前的最右端的可匹配到一对 ((a,a*x)) 的左端点位置，两者的更新显然。
那么我们把询问离线到每一个对应的 (x) 处，处理完当前的 (res) 数组后，我们直接可以 (O(1)) 回答每一个询问。（直接查询右端点的 (res[r]) 是否大于等于 (l) 即可）
时间复杂度 (O(nsqrt{n}+frac{nm}{w})) 。
代码
#include<bits/stdc++.h>
using namespace std;
//#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//char buf[1<<21],*p1=buf,*p2=buf;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)){if(ch=='-'){f=true;}ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return ;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
return ;
}
const int N=1e5+5,V=1e5;
#define ll long long
int n,m,k;
int bl[N];
int a[N],cnt[N],Ans[N],stk[N],top,pos[N],Cnt1,Cnt2;
struct Query{int op,l,r,v,id;}Q[N],Q1[N];
int Now,Num;
bitset<N<<1> Now1,Now2,tmp;
inline void Add(int x){
cnt[x]++;
Now1.set(x+V),Now2.set(V-x);
return ;
}
inline void Del(int x){
cnt[x]--;
if(!cnt[x]) Now1.reset(x+V),Now2.reset(V-x);
return ;
}
inline bool Cmp(Query x,Query y){return bl[x.l]^bl[y.l]?bl[x.l]<bl[y.l]:bl[x.l]&1?x.r<y.r:x.r>y.r;}
vector<int> v[N];
inline bool Ask(int x){
for(int i=0;i<v[x].size();i++){
int y=v[x][i];
if(cnt[y]&&cnt[x/y]) return true;
}
return false;
}
inline bool Ask1(int x){
for(int i=1;i<=V/x;i++) if(cnt[i]&&cnt[i*x]) return true;
return false;
}
int las[N],res[N];
vector<Query> vec[N];
int main(){
for(int i=1;i<=V;i++) for(int j=i;j<=V;j+=i) v[j].push_back(i);
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
const int t=sqrt(n),lim=sqrt(V);
for(int i=1;i<=m;i++){
int op,l,r,x;
read(op),read(l),read(r),read(x);
if(op==4&&x<=lim) vec[x].push_back(Query{4,l,r,x,i});
else Q[++Cnt1]=Query{op,l,r,x,i};
}
for(int x=1;x<=lim;x++){
if(vec[x].empty()) continue;
for(int i=0;i<=V;i++) las[i]=res[i]=0;
int l=0;
for(int i=1;i<=n;i++){
las[a[i]]=i;
if(a[i]*x<=V) l=max(l,las[a[i]*x]);
if(a[i]%x==0) l=max(l,las[a[i]/x]);
res[i]=l;
}
int len=vec[x].size();
for(int i=0;i<len;i++){
Query t=vec[x][i];
Ans[t.id]=(res[t.r]>=t.l);
}
}
for(int i=1;i<=n;i++) bl[i]=(i-1)/t+1;
sort(Q+1,Q+Cnt1+1,Cmp);
int l=1,r=0;
for(int i=1;i<=Cnt1;i++){
while(l>Q[i].l) Add(a[--l]);
while(r<Q[i].r) Add(a[++r]);
while(l<Q[i].l) Del(a[l++]);
while(r>Q[i].r) Del(a[r--]);
if(Q[i].op==1) tmp=(Now1>>Q[i].v)&Now1,Ans[Q[i].id]=tmp.any();
else if(Q[i].op==2) tmp=(Now1>>Q[i].v)&Now2,Ans[Q[i].id]=tmp.any();
else if(Q[i].op==3) Ans[Q[i].id]=Ask(Q[i].v);
else Ans[Q[i].id]=Ask1(Q[i].v);
}
for(int i=1;i<=m;i++) puts(Ans[i]?"yuno":"yumi");
return 0;
}