做此题前请自行科普一下 bitset。
大概就是一个状态压缩的东西。
这题很强势啊……
Orz lxl!
我们设 \(cnt_1\) 表示每个数是否存在的 bitset，设 \(cnt_2\) 表示 \(cnt_1\) 整体反转的结果。
操作 \(1\) 相当于判断是否存在 \(y - z = x\)，也就是是否同时存在 \(y\) 与 \(y - x\)。
这个比较简单，用 \(cnt_1\) 与其左移 \(x\) 位的结果按位与，如果结果 \(> 0\) 则存在。
操作 \(2\) 相当于判断是否存在 \(y + z = x\)。
对于任意整数 \(w\)，我们设 \(w^\prime\) 表示 \(cnt_2\) 中 \(w\) 存储的位置，即 \(c - w\)。
那么
\[\begin{align*} y + z & = x\\ y + c - z^\prime & = x\\ y + c & = x + z^\prime\\ z^\prime & = y + c - x \end{align*}\]
也就是是否同时存在 \(y\) 与 \((y + c - x)^\prime\)。 所以把 \(cnt_1\) 与 \(cnt_2\) 右移 \(c - x\) 位的结果按位与，如果结果 \(> 0\) 则存在。
操作 \(3\)？暴力枚举两个因数啊！反正 \(O(\sqrt{a_i})\) 随便跑。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
const int N = 1e5;
const int M = 1e5;
const int C = 1e5;
int n,m,block,pos[N + 10],a[N + 10];
int ans[M + 10],cnt[C + 10];
bitset<C + 10> cur[2];
struct s_query
{
int op,l,r,x,id;
inline bool operator<(const s_query &a) const
{
return pos[l] < pos[a.l] || (pos[l] == pos[a.l] && r < a.r);
}
} qry[M + 10];
int main()
{
scanf("%d%d",&n,&m);
block = pow(n,2.0 / 3);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),pos[i] = (i - 1) / block + 1;
for(register int i = 1;i <= m;++i)
scanf("%d%d%d%d",&qry[i].op,&qry[i].l,&qry[i].r,&qry[i].x),qry[i].id = i;
sort(qry + 1,qry + m + 1);
for(register int i = 1,l = 1,r = 0;i <= m;++i)
{
while(r < qry[i].r)
{
++r;
if(!cnt[a[r]]++)
cur[0][a[r]] = 1,cur[1][C - a[r]] = 1;
}
while(r > qry[i].r)
{
if(!--cnt[a[r]])
cur[0][a[r]] = 0,cur[1][C - a[r]] = 0;
--r;
}
while(l < qry[i].l)
{
if(!--cnt[a[l]])
cur[0][a[l]] = 0,cur[1][C - a[l]] = 0;
++l;
}
while(l > qry[i].l)
{
--l;
if(!cnt[a[l]]++)
cur[0][a[l]] = 1,cur[1][C - a[l]] = 1;
}
if(qry[i].op == 1)
ans[qry[i].id] = (cur[0] & (cur[0] << qry[i].x)).any();
else if(qry[i].op == 2)
ans[qry[i].id] = (cur[0] & (cur[1] >> C - qry[i].x)).any();
else
for(register int j = 1;j * j <= qry[i].x && !ans[qry[i].id];++j)
if(!(qry[i].x % j))
ans[qry[i].id] = cur[0][j] & cur[0][qry[i].x / j];
}
for(register int i = 1;i <= m;++i)
puts(ans[i] ? "hana" : "bi");
}