Description
由乃在自己的农田边散步，她突然发现田里的一排玉米非常的不美。这排玉米一共有N株，它们的高度参差不齐。由乃认为玉米田不美，所以她决定出个数据结构题 这个题是这样的：给你一个序列a，长度为n，有m次操作，每次询问一个区间是否可以选出两个数它们的差为x，或者询问一个区间是否可以选出两个数它们的和为x，或者询问一个区间是否可以选出两个数它们的乘积为x ，这三个操作分别为操作1,2,3选出的这两个数可以是同一个位置的数
Input
第一行两个数n,m后面一行n个数表示ai后面m行每行四个数opt l r xopt表示这个是第几种操作，l,r表示操作的区间，x表示这次操作的x定义c为每次的x和ai中的最大值，ai >= 0，每次的x>=2n,m,c <= 100000
Output
对于每个询问，如果可以，输出yuno，否则输出yumi
Sample Input
5 5
1 1 2 3 4
2 1 1 2
1 1 2 2
3 1 1 1
3 5 5 16
1 2 3 4
Sample Output
yuno
yumi
yuno
yuno
yumi
正解：莫队算法+$bitset$。
这题坑点巨多，数据范围都没给全。。
我们考虑莫队算法，把询问排个序就行了。如何统计答案？如果是两个数相乘等于$x$的情况，我们直接暴力枚举因子就行了。如果是两个数相减等于$x$的情况，我们把每个数压到$bitset$上，直接看$a[i]$的那个$bitset$数组右移$x$位以后再与一下原数组，如果不为0那么显然是有解的。如果是加法的话，我们考虑用另一个$bitset$来压$b[i]$，其中$b[i]$表示$c-a[i]$，其中$c$为$a[i]$的最大值。那么只要$a[i]=b[j]+x-c$，那就是有解的。于是我们把这个$bitset$数组右移$c-x$位，再与$a$数组的$bitset$数组与一下就行了。
//It is made by wfj_2048~
#include <algorithm>
#include <iostream>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define inf (1<<30)
#define N (1000010)
#define il inline
#define RG register
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) using namespace std; struct node{ int i,opt,l,r,x; }q[N]; int cnt[N],bl[N],ans[N],a[N],b[N],n,m,mc,block; bitset <> f,g,h; il int gi(){
RG int x=,q=; RG char ch=getchar();
while ((ch<'' || ch>'') && ch!='-') ch=getchar();
if (ch=='-') q=-,ch=getchar();
while (ch>='' && ch<='') x=x*+ch-,ch=getchar();
return q*x;
} il int cmp(const node &a,const node &b){
if (bl[a.l]==bl[b.l]) return a.r<b.r;
return bl[a.l]<bl[b.l];
} il void add(RG int x){
cnt[a[x]]++;
if (cnt[a[x]]==) f[a[x]]=,g[b[x]]=;
return;
} il void del(RG int x){
cnt[a[x]]--;
if (!cnt[a[x]]) f[a[x]]=,g[b[x]]=;
return;
} il int check(RG int opt,RG int x){
if (opt==){
h=f,h>>=x,h&=f;
if (h.count()) return ;
}
if (opt==){
h=g,h>>=abs(mc-x),h&=f;
if (h.count()) return ;
}
if (opt==){
RG int lim=sqrt(x+);
for (RG int i=;i<=lim;++i){
if (x%i) continue;
if (cnt[i] && cnt[x/i]) return ;
}
}
return ;
} il void work(){
n=gi(),m=gi(),block=sqrt(n),mc=;
for (RG int i=;i<=n;++i)
a[i]=gi(),b[i]=mc-a[i],bl[i]=(i-)/block+;
for (RG int i=;i<=m;++i)
q[i].i=i,q[i].opt=gi(),q[i].l=gi(),q[i].r=gi(),q[i].x=gi();
sort(q+,q+m+,cmp); RG int L=q[].l,R=q[].r;
for (RG int i=L;i<=R;++i) add(i); ans[q[].i]=check(q[].opt,q[].x);
for (RG int i=;i<=m;++i){
while (L>q[i].l) add(--L);
while (R<q[i].r) add(++R);
while (L<q[i].l) del(L++);
while (R>q[i].r) del(R--);
ans[q[i].i]=check(q[i].opt,q[i].x);
}
for (RG int i=;i<=m;++i)
puts(ans[i] ? "yuno" : "yumi");
return;
} int main(){
File("yn");
work();
return ;
}
