题解：P5355 [Ynoi Easy Round 2017] 由乃的玉米田
简单的一道 Ynoi。
写了半个多小时还能调了一个小时也是无敌了。
思路
以下称值域为
我是彩笔，不会在线，所以首先跑个莫队是肯定的。
前三个操作很简单十分容易处理。
维护两个 bitset
-
-
-
-
~~因为我做过 GOSICK，看到倍数显然根号分治。~~ 考虑用根号分治来处理这类询问。设阈值为 $T$。 当 $x > T$，直接暴力枚举 $ka$ 做到一个询问 $O(\frac{n}{T})$。 当 $x \le T$，我们不在莫队中解决，放到外面来做。此时 $x$ 只有 $T$ 种取值，考虑用 $O(n)$ 的复杂度来做一个 $x$。 对于一个 $x$，处理两个数组 $las$ 和 $pre$，$las_{i}$ 表示值为 $a_{i} \times x$ 的下一个数，$pre_{i}$ 表示值为 $a_{i} \times x$ 的上一个数。 那么对于一个询问 $[l,r]$，区间内 $las$ 最小值小于 $r$，或是 $pre$ 最大值大于 $l$，就存在答案。拿一个喜欢的数据结构维护一下就可以了，我用的分块处理每个询问 $O(\sqrt{n})$。
于是做完了，复杂度是
::::success[code]
/*
——我们的时间，就这样开始了。
海风吹拂着面颊……纯白色的羽毛从天空中降下。
我们手牵着手仰望着天空，立下要去恋爱的誓言————
*/
#include<bits/stdc++.h>
//#pragma GCC optimize(1,2,3,"Ofast","inline")
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define inf 2000000000
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return x*f;
}
int n,q;
int s[100010],a[100010];
bitset<200010> p,pp;
int ans[200010];
struct Q{int opt,l,r,x,id;}qs[100010];
int B,bel[100010];
inline bool cmpQ(Q x,Q y){
if(bel[x.l]!=bel[y.l])return x.l<y.l;
if(bel[x.l]&1)return x.r>y.r;
return x.r<y.r;
}
int l=1,r=0;
inline void ldel(){
int x=--l;
if(!s[a[x]])p.flip(a[x]),pp.flip(1e5-a[x]);
s[a[x]]++;
}
inline void radd(){
int x=++r;
if(!s[a[x]])p.flip(a[x]),pp.flip(1e5-a[x]);
s[a[x]]++;
}
inline void ladd(){
int x=l++;
s[a[x]]--;
if(!s[a[x]])p.flip(a[x]),pp.flip(1e5-a[x]);
}
inline void rdel(){
int x=r--;
s[a[x]]--;
if(!s[a[x]])p.flip(a[x]),pp.flip(1e5-a[x]);
}
int T=0,V;
int las[100010],pre[100010];
int tagl[1000],tagp[1000];
vector<int> qq[1000];
inline int qryp(int l,int r){
int LL=bel[l],RR=bel[r];
int Rl=LL*B,Lr=(RR-1)*B+1;
int ans=0;
if(LL==RR){
for(int i=l;i<=r;i++)ans=max(ans,pre[i]);
}
else {
for(int i=l;i<=Rl;i++)ans=max(ans,pre[i]);
for(int i=Lr;i<=r;i++)ans=max(ans,pre[i]);
for(int i=LL+1;i<=RR-1;i++)ans=max(ans,tagp[i]);
}
return ans;
}
inline int qryl(int l,int r){
int LL=bel[l],RR=bel[r];
int Rl=LL*B,Lr=(RR-1)*B+1;
int ans=inf;
if(LL==RR){
for(int i=l;i<=r;i++)ans=min(ans,las[i]);
}
else {
for(int i=l;i<=Rl;i++)ans=min(ans,las[i]);
for(int i=Lr;i<=r;i++)ans=min(ans,las[i]);
for(int i=LL+1;i<=RR-1;i++)ans=min(ans,tagl[i]);
}
return ans;
}
signed main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
n=read(),q=read();
for(int i=1;i<=n;i++)a[i]=read(),V=max(a[i],V);
for(int i=1;i<=q;i++)qs[i].opt=read(),qs[i].l=read(),qs[i].r=read(),qs[i].x=read(),qs[i].id=i;
B=sqrt(n);T=B;
for(int i=1;i<=n;i++)bel[i]=(i-1)/B+1;
sort(qs+1,qs+q+1,cmpQ);
for(int i=1;i<=q;i++){
while(l>qs[i].l)ldel();
while(r<qs[i].r)radd();
while(l<qs[i].l)ladd();
while(r>qs[i].r)rdel();
if(qs[i].opt==1)if(((p>>qs[i].x)&p).any())ans[qs[i].id]=1;
if(qs[i].opt==2)if(((pp>>(1e5-qs[i].x))&p).any())ans[qs[i].id]=1;
if(qs[i].opt==3){
for(int j=1;j<=sqrt(qs[i].x);j++)
if(qs[i].x%j==0&&s[j]&&s[qs[i].x/j]){ans[qs[i].id]=1;break;}
}
if(qs[i].opt==4){
if(qs[i].x>T){
for(int j=1;j*qs[i].x<=V;j++)
if(s[j]&&s[j*qs[i].x]){ans[qs[i].id]=1;break;}
}
else qq[qs[i].x].push_back(i);
}
if(qs[i].opt==4&&qs[i].x==1)ans[qs[i].id]=1;
}
for(int k=2;k<=T;k++){
for(int i=1;i<=1000;i++)tagl[i]=inf;
for(int i=1;i<=1000;i++)tagp[i]=0;
memset(s,0,sizeof s);
for(int i=1;i<=n;i++)
if(a[i]*k<=V)pre[i]=s[a[i]*k],s[a[i]]=i;
else pre[i]=0,s[a[i]]=i;
for(int i=1;i<=V;i++)s[i]=inf;
for(int i=n;i>=1;i--)
if(a[i]*k<=V)las[i]=s[a[i]*k],s[a[i]]=i;
else las[i]=inf,s[a[i]]=i;
for(int i=1;i<=n;i++){
tagl[bel[i]]=min(tagl[bel[i]],las[i]);
tagp[bel[i]]=max(tagp[bel[i]],pre[i]);
}
for(int i=0;i<qq[k].size();i++){
int x=qq[k][i];
int mx=qryp(qs[x].l,qs[x].r),mn=qryl(qs[x].l,qs[x].r);
if((mx!=0&&mx>=qs[x].l)||(mn!=inf&&mn<=qs[x].r))ans[qs[x].id]=1;
}
}
for(int i=1;i<=q;i++)if(ans[i])cout<<"yuno\n";else cout<<"yumi\n";
return 0;
}::::