Description：

给一个序列，每次询问一个区间是否可以选出两个数它们的差 $/$ 和 $/$ 乘积为 $x$ 。

$1\leqslant n,a[i]\leqslant 100000$

Solution：

分析一下莫队的性质，虽然左右端点会变动 $O(n\sqrt n)$ 次，也就是说单点加入或者删除必须是 $O(1)$ 的，至少是 $O(\log n)$ 的，但是查询一共只有 $O(q)$ 次，也就是说我们可以牺牲查询的复杂度来保证修改的复杂度。

于是这题用两个 $bitset$ 来维护每个数字是否出现，一个为 $x$ 一个为 $100000-x$ ，然后左右移 $\&$ 就可以 $O(100000/64)$ 解决前两个问题了，乘积的话直接 $O(\sqrt x)$ 暴力枚举就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<bitset>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

int val[MAXN];

#define N 100000

int cnt[MAXN];

bitset<MAXN> num,rev;

struct query

{

	int opt,l,r,x,id,ans;

}q[MAXN];

int pos[MAXN];

bool cmp(query a,query b){return (pos[a.l] == pos[b.l] ? a.r < b.r : a.l < b.l);}

bool cmp_id(query a,query b){return a.id < b.id;}

void add(int v)

{

	++cnt[v];

	num[v] = rev[N - v] = true;

	return;

}

void rem(int v)

{

	--cnt[v];

	if(cnt[v] == 0)num[v] = rev[N - v] = false;

	return;

}

int calc(int opt,int x)

{

	if(opt == 1)

	{

		if((num & (num >> x)).count())return 1;

		else return 0;

	}

	if(opt == 2)

	{

		if(((rev >> (N - x)) & num).count())return 1;

		else return 0;

	}

	if(opt == 3)

	{

		for(int i = 1;i * i <= x;++i)

		{

			if(x % i == 0)

			{

				if(num[i] && num[x / i])return 1;

			}

		}

		return 0;

	}

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&val[i]);

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d",&q[i].opt,&q[i].l,&q[i].r,&q[i].x);

		q[i].id = i;

	}

	int blo = sqrt(n);

	for(int i = 1;i <= n;++i)pos[i] = (i - 1) / blo + 1;

	sort(q + 1,q + 1 + m,cmp);

	for(int i = 1,l = 1,r = 0;i <= m;++i)

	{

		while(r < q[i].r)add(val[++r]);

		while(l > q[i].l)add(val[--l]);

		while(r > q[i].r)rem(val[r--]);

		while(l < q[i].l)rem(val[l++]);

		q[i].ans = calc(q[i].opt,q[i].x);

	}

	sort(q + 1,q + 1 + m,cmp_id);

	for(int i = 1;i <= m;++i)

	{

		if(q[i].ans)puts("hana");

		else puts("bi");

	}

	return 0;

}