莫队+$bitset$优化
操作$1$：
维护一个$bitset:$ $cnt1$.$cnt1_i$表示$i$这个数是否出现
若存在数$y,z$使得$y-z=x$,则$y = z + x$
故将$cnt1$与($cnt1<<x$)做与运算即可
操作$2$：
维护两个$bitset: cnt1,cnt2$.
$cnt1_i$表示$i$这个数是否出现,$cnt2_i$表示$MaxN-i$这个数是否出现
若存在数$y,z$使得$y+z=x$,则有$y + z - MaxN= x - MaxN$
令$z’=MaxN-z$，则原式转化为$y - z’ = x - MaxN$
那么就变成了操作1了。。。只不过这次在cnt2中查$z’$
故将$cnt1$与$(cnt2>>($MaxN-x$))$做与运算即可(为什么右移$MaxN-x$位呢？因为cnt2和cnt1是反着存储的)
操作$3$：
暴力枚举$x$的约数查询即可
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <bits/stdc++.h>
const int MaxN = 100010;
struct query
{
int id, pos;
int op, l, r, x;
};
query q[MaxN];
int n, m, size;
int a[MaxN], cnt[MaxN], ans[MaxN];
std::bitset<100010> cnt1, cnt2;
inline int cmp(query a, query b)
{
if (a.pos != b.pos)
return a.pos < b.pos;
else
return a.r < b.r;
}
inline int read()
{
int x = 0;
char ch = getchar();
while (ch > '9' || ch < '0')
ch = getchar();
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return x;
}
inline void add(int x)
{
++cnt[a[x]];
if(cnt[a[x]] == 1)
cnt1[a[x]] = 1, cnt2[100000 - a[x]] = 1;
}
inline void del(int x)
{
--cnt[a[x]];
if(cnt[a[x]] == 0)
cnt1[a[x]] = 0, cnt2[100000 - a[x]] = 0;
}
inline void solve()
{
int l = 1, r = 0;
for (int i = 1; i <= m; i++)
{
while (l > q[i].l)
--l, add(l);
while (r < q[i].r)
++r, add(r);
while (l < q[i].l)
del(l), ++l;
while (r > q[i].r)
del(r), --r;
if (q[i].op == 1)
ans[q[i].id] = (cnt1 & (cnt1 << q[i].x)).any();
else if (q[i].op == 2)
ans[q[i].id] = (cnt1 & (cnt2 >> (100000 - q[i].x))).any();
else if (q[i].op == 3)
{
for (int j = 1; j * j <= q[i].x; j++)
{
if (q[i].x % j == 0)
if (cnt1[j] && cnt1[q[i].x / j])
ans[q[i].id] = 1;
}
}
}
}
int main()
{
n = read(), m = read();
size = pow(n, 0.55);
for (int i = 1; i <= n; i++)
a[i] = read();
for (int i = 1; i <= n; i++)
{
q[i].op = read(), q[i].l = read(), q[i].r = read(), q[i].x = read();
q[i].id = i, q[i].pos = (q[i].l - 1) / size + 1;
}
std::sort(q + 1, q + m + 1, cmp);
solve();
for (int i = 1; i <= m; i++)
puts(ans[i] == 1 ? "hana" : "bi");
return 0;
}
|