【洛谷5355】[Ynoi2017] 由乃的玉米田（莫队+bitset）
- 给定一个长度为(n)的序列。
- (q)次询问，每次要求判断一段区间是否能选出两个数（可以在同一位置），使得这两个数为差(x)/和为(x)/积为(x)/商为(x)（无余数）。
- (n,q,Vle10^5)
减、加、乘的简单莫队
只有加、减、乘操作的话是非常水的。
我们只要维护好两个(bitset)，分别记录每个数(v)的存在性（(s1)）和每个数的相反数(MAX-v)的存在性（(s2)）。
对于减法，我们把(s1)左移(x)位（相当于给所有数加上了(x)），然后和(s1)按位与在一起，如果依然有(1)，就说明这两个数差为(x)。
对于加法，我们把(s1)左移(MAX-x)和(s2)按位与在一起，如果有(1)，就说明(v1+MAX-x=MAX-v2)，移项便可见这两个数和为(x)。
对于乘法，我们直接暴力枚举它的所有小于等于(O(sqrt n))的因子，然后只要到(bitset)中询问是否同时存在一对乘起来等于(x)的因子即可。由于这个复杂度和莫队是独立的，因此也是正确的。
除法的根号分治
首先考虑如果询问的(x)大于(sqrt {MAX})，我们可以把它放到前面的莫队里一起做，只要(O(sqrt {MAX}))暴力枚举倍数判断是否存在即可。
否则那么(xlesqrt{MAX})，那么我们只要枚举每种(x)分别暴力即可。
具体我们把询问离线按右端点排序，向右扫的过程中维护好每个数上次出现的位置(lst_v)，然后考虑如果一个位置(i)能作为右端点产生贡献，当且仅当在(i)之前最后一个(a_i imes x)或(a_idiv x)所在的位置（可以直接询问(lst)）和(i)都在区间内。
所以我们枚举右端点，每次将当前位置计入可以考虑的范围，然后就只要维护最大的左边能产生贡献的位置(t)，每次询问是判一下询问的左端点是否小于等于(t)即可。
(O(nsqrt n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define S 320
#define Gmax(x,y) (x<(y)&&(x=(y)))
using namespace std;
int n,m,a[N+5],sz,bl[N+5],ans[N+5];
namespace FastIO
{
#define FS 100000
#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
char oc,FI[FS],*FA=FI,*FB=FI;
Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
}using namespace FastIO;
namespace Mo//莫队处理减、加、乘、大数除
{
int Qt;struct Q
{
int p,l,r,op,x;I Q(CI i=0,CI a=0,CI b=0,CI g=0,CI v=0):p(i),l(a),r(b),op(g),x(v){}
I bool operator < (Con Q& o) Con {return bl[l]^bl[o.l]?l<o.l:(bl[l]&1?r>o.r:r<o.r);}
}q[N+5];
int c[N+5];bitset<N+5> s1,s2;I void Solve()
{
RI i,j,L=1,R=0;for(sort(q+1,q+Qt+1),i=1;i<=Qt;++i)
{
#define A(x) (!c[x]++&&(s1.set(x),s2.set(N-x),0))
#define D(x) (!--c[x]&&(s1.reset(x),s2.reset(N-x),0))
W(R<q[i].r) ++R,A(a[R]);W(L>q[i].l) --L,A(a[L]);W(R>q[i].r) D(a[R]),--R;W(L<q[i].l) D(a[L]),++L;//移动区间
if(q[i].op==1) {ans[q[i].p]=((s1<<q[i].x)&s1).any();continue;}//减法
if(q[i].op==2) {ans[q[i].p]=((s1<<N-q[i].x)&s2).any();continue;}//加法
if(q[i].op==3) {if(!q[i].x) ans[q[i].p]=s1.test(0);else for(j=1;j*j<=q[i].x;++j)//乘法
if(!(q[i].x%j)&&s1.test(j)&&s1.test(q[i].x/j)) {ans[q[i].p]=1;break;}continue;}//枚举一对因数判断
for(j=1;q[i].x*j<=N;++j) if(s1.test(j)&&s1.test(q[i].x*j)) {ans[q[i].p]=1;break;}//除法，暴枚倍数
}
}
}
namespace BF//暴力处理小数除
{
struct Q
{
int p,l,r;I Q(CI i=0,CI a=0,CI b=0):p(i),l(a),r(b){}
I bool operator < (Con Q& o) Con {return r<o.r;};
};vector<Q> q[S+5];
int lst[N+5];I void Solve(CI x)
{
RI i,j=0,qs=q[x].size(),t=0;for(sort(q[x].begin(),q[x].end()),i=0;i<=N;++i) lst[i]=0;//按右端点排序，清空lst
for(i=1;i<=n;lst[a[i]]=i,++i) {a[i]*x<=N&&Gmax(t,lst[a[i]*x]),//a[i]×x
!(a[i]%x)&&Gmax(t,lst[a[i]/x]);W(j^qs&&q[x][j].r==i) ans[q[x][j].p]=q[x][j].l<=t,++j;}//a[i]÷x，询问只要将左端点与t比较
}
}
int main()
{
RI i,j;for(read(n),read(m),sz=sqrt(n),i=1;i<=n;++i) read(a[i]),bl[i]=(i-1)/sz+1;
RI op,l,r,x;for(i=1;i<=m;++i) read(op,l,r,x),op^4||x>S
?(Mo::q[++Mo::Qt]=Mo::Q(i,l,r,op,x),0):(x^1?(BF::q[x].push_back(BF::Q(i,l,r)),0):ans[i]=1);//把询问分类
for(Mo::Solve(),i=2;i<=S;++i) !BF::q[i].empty()&&(BF::Solve(i),0);//先统一莫队，再枚举小除数暴力
for(i=1;i<=m;++i) puts(ans[i]?"yuno":"yumi");return 0;
}