当前位置：首页 > news >正文

BF的数据结构题单-省选根号数据结构 - 题单 - 洛谷计算机科学教育新生态

news 2025/6/30 6:37:07

BF的数据结构题单-省选根号数据结构 - 题单 - 洛谷 | 计算机科学教育新生态

莫队初步部分题解：

** P2709 小B的询问 - 洛谷 *

P2709 小B的询问

题目描述

小B 有一个长为 n的整数序列 a，值域为 [1,k]。
他一共有 m个询问，每个询问给定一个区间 [l,r]，求：

$\sum\limits_{i=1}^k c_i^2$
其中 c_i表示数字 i$在 [l,r] 中的出现次数。
小B请你帮助他回答询问。

题目解析

这是一道典型的莫队算法入门题。我们需要在区间的移动过程中，高效地维护
$\sum c_i^2$
的值。

莫队算法的核心思想是通过对询问进行分块和排序，来优化区间端点移动的总次数。对于维护答案，我们只需要考虑当区间端点移动一格时，答案会如何变化。

假设当前维护的答案是 ans，我们现在要将一个数 x（其值为 val = a[x]）加入区间。
在加入 x 之前，val 在区间中出现了 cnt[val] 次，它对答案的贡献是 cnt[val]^2。
加入 x 之后，val 在区间中出现了 cnt[val] + 1 次，它对答案的贡献变为 (cnt[val] + 1)^2。
因此，总答案的变化量为 (cnt[val] + 1)^2 - cnt[val]^2 = 2 * cnt[val] + 1。

我们可以通过以下步骤更新答案：

从总答案中减去旧的贡献：ans -= cnt[val] * cnt[val]
更新该值的出现次数：cnt[val]++
向总答案中加入新的贡献：ans += cnt[val] * cnt[val]

同理，当我们将一个数 x（其值为 val = a[x]）从区间中删除时：

从总答案中减去旧的贡献：ans -= cnt[val] * cnt[val]
更新该值的出现次数：cnt[val]--
向总答案中加入新的贡献：ans += cnt[val] * cnt[val]

通过这两个操作，我们可以在 $O (1)$ 的时间内完成区间的扩展和收缩。配合莫队的奇偶性排序优化，总时间复杂度为 $O(n\sqrt{m})$ 。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)struct Query {int l, r, index;long long ans;
};int n, m, k;
const int N = 5e4 + 10;
int a[N];
int belong[N];
int B;
long long current_ans = 0;
int cnt[N];void add(int x) {// a[x] 是要加入的数的值current_ans -= cnt[a[x]] * cnt[a[x]];cnt[a[x]]++;current_ans += cnt[a[x]] * cnt[a[x]];
}void del(int x) {// a[x] 是要删除的数的值current_ans -= cnt[a[x]] * cnt[a[x]];cnt[a[x]]--;current_ans += cnt[a[x]] * cnt[a[x]];
}void solve() {cin >> n >> m >> k;B = sqrt(n);for (int i = 1; i <= n; i++) {cin >> a[i];belong[i] = (i - 1) / B + 1;}vector<Query> queries(m);for (int i = 0; i < m; i++) {cin >> queries[i].l >> queries[i].r;queries[i].index = i;}sort(queries.begin(), queries.end(), [&](const Query &x, const Query &y) {if (belong[x.l] != belong[y.l]) {return belong[x.l] < belong[y.l];}// 奇偶性排序优化if (belong[x.l] % 2) {return x.r < y.r;}return x.r > y.r;});int L = 1, R = 0;for (int i = 0; i < m; i++) {int ql = queries[i].l;int qr = queries[i].r;while (L > ql) add(--L);while (R < qr) add(++R);while (L < ql) del(L++);while (R > qr) del(R--);queries[i].ans = current_ans;}sort(queries.begin(), queries.end(), [&](const Query &x, const Query &y) {return x.index < y.index;});for (int i = 0; i < m; i++) {cout << queries[i].ans << endl;}
}signed main() {close;solve();return 0;
}

P1494 [国家集训队] 小 Z 的袜子 - 洛谷

P1494 [国家集训队] 小 Z 的袜子

题目描述

小 Z 把这 $N$ 只袜子从 $1$ 到 $N$ 编号，然后从编号 $L$ 到 $R$ 的袜子中随机选出两只来穿。你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。

数据中有 $L = R$ 的情况，请特判这种情况，输出0/1。

题目解析

这道题要求计算一个区间内随机取两个数相等的概率。

设区间 $[l, r]$ 的长度为 len = r - l + 1。
从 len 只袜子中随机取两只，总方案数是组合数
$\binom{\text{len}}{2} = \frac{\text{len} \times (\text{len}-1)}{2}$
。
设颜色 i 在区间内出现了 c_i 次。从中取出两只颜色为 i 的袜子的方案数是
$\binom{c_i}{2} = \frac{c_i \times (c_i-1)}{2}$
。
因此，取出两只颜色相同袜子的总方案数是
$\sum \binom{c_i}{2}$
。
概率
$\frac{\sum \binom{c_i}{2}}{\binom{\text{len}}{2}} = \frac{\sum \frac{c_i(c_i-1)}{2}}{\frac{\text{len}(\text{len}-1)}{2}} = \frac{\sum (c_i^2 - c_i)}{\text{len}(\text{len}-1)}$
。
注意到 \sum c_i就是区间的总长度 len。所以公式可以化为
$\frac{(\sum c_i^2) - \text{len}}{\text{len}(\text{len}-1)}$
。

观察分子，我们发现核心问题和上一题一样，都是维护 sum c_i^2。我们可以用完全相同的莫队 add 和 del 函数来维护这个值。
对于每个询问，我们用莫队算法求出其 sum c_i^2 的值，然后代入公式计算概率。
分母是 len * (len-1)，分子是 (Σc_i^2) - len。
最后，用 gcd 对分数进行约分即可。

特殊情况：

当 len < 2（即 l == r）时，无法选出两只袜子，此时分子为0，概率为0。根据题意输出 0/1。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)struct Query {int l, r, index;
};const int N = 5e4 + 10;
int n, m;
int c[N];
int belong[N], B;
int cnt[N];
long long ans_numerator;
long long ans[N];long long gcd(long long a, long long b) {return b == 0 ? a : gcd(b, a % b);
}void add(int x) {ans_numerator -= cnt[c[x]] * (cnt[c[x]] - 1) / 2;cnt[c[x]]++;ans_numerator += cnt[c[x]] * (cnt[c[x]] - 1) / 2;
}void del(int x) {ans_numerator -= cnt[c[x]] * (cnt[c[x]] - 1) / 2;cnt[c[x]]--;ans_numerator += cnt[c[x]] * (cnt[c[x]] - 1) / 2;
}void solve() {cin >> n >> m;B = sqrt(n);for (int i = 1; i <= n; i++) {cin >> c[i];belong[i] = (i - 1) / B + 1;}vector<Query> queries(m);vector<pair<long long, long long>> results(m);for (int i = 0; i < m; i++) {cin >> queries[i].l >> queries[i].r;queries[i].index = i;}sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {if (belong[a.l] != belong[b.l]) return belong[a.l] < belong[b.l];if (belong[a.l] % 2) return a.r < b.r;return a.r > b.r;});int L = 1, R = 0;for (int i = 0; i < m; i++) {int ql = queries[i].l, qr = queries[i].r;if (ql == qr) {results[queries[i].index] = {0, 1};continue;}while (L > ql) add(--L);while (R < qr) add(++R);while (L < ql) del(L++);while (R > qr) del(R--);long long len = qr - ql + 1;long long denominator = len * (len - 1) / 2;long long common = gcd(ans_numerator, denominator);results[queries[i].index] = {ans_numerator / common, denominator / common};}for (int i = 0; i < m; i++) {cout << results[i].first << "/" << results[i].second << endl;}
}signed main() {close;solve();return 0;
}

P4462 [CQOI2018] 异或序列 - 洛谷

P4462 [CQOI2018] 异或序列

题目描述

已知一个长度为 n 的整数数列 a_1,a_2，给定查询参数 l,r，问在 a_l,a_{l+1} 区间内，有多少子区间满足异或和等于 k。

题目解析

这道题需要处理区间的异或和。处理异或和问题，通常的技巧是使用 前缀异或和。
令
$a_1 \oplus a_2 \oplus \dots \oplus a_i$
，并规定
$s [0] = 0$
。
那么，区间
$[x, y]$
的异或和可以表示为
$\oplus s[x-1]$
。

题目要求我们找到满足
$\leq x \leq y \leq r$
且
$\oplus s[x-1] = k 的数对 (x, y)$
的数量。
这个条件可以变形为
$\oplus k$
。

问题转化为：对于一个查询 [l, r]，我们需要统计满足
$\leq x \leq y \leq r$
且
$\oplus k$
的数对 (x, y) 的数量。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)struct Query {int l, r, index;
};const int N = 1e5 + 10;
int n, m, k;
int a[N], s[N];
int belong[N], B;
long long cnt[N * 2]; // 异或和的值可能较大
long long current_ans = 0;
long long ans[N];void add(int x) {current_ans += cnt[s[x] ^ k];cnt[s[x]]++;
}void del(int x) {cnt[s[x]]--;current_ans -= cnt[s[x] ^ k];
}void solve() {cin >> n >> m >> k;s[0] = 0;for (int i = 1; i <= n; i++) {cin >> a[i];s[i] = s[i - 1] ^ a[i];}B = sqrt(n);vector<Query> queries(m);for (int i = 0; i < m; i++) {cin >> queries[i].l >> queries[i].r;queries[i].index = i;belong[i] = (queries[i].l - 1) / B;}sort(queries.begin(), queries.end(), [&](const Query& x, const Query& y) {int block_x = (x.l - 1) / B;int block_y = (y.l - 1) / B;if (block_x != block_y) return block_x < block_y;if (block_x % 2) return x.r < y.r;return x.r > y.r;});int L = 1, R = 0;for (int i = 0; i < m; i++) {int ql = queries[i].l, qr = queries[i].r;// 莫队维护的是s数组的区间[ql-1, qr]while (L > ql - 1) add(--L);while (R < qr) add(++R);while (L < ql - 1) del(L++);while (R > qr) del(R--);ans[queries[i].index] = current_ans;}for (int i = 0; i < m; i++) {cout << ans[i] << endl;}
}signed main() {close;solve();return 0;
}

P3709 大爷的字符串题 - 洛谷

P3709 大爷的字符串题

题目描述

给你一个字符串 $a$ （实际上是数字序列），每次询问一段区间的贡献。贡献定义：每次从这个区间中拿出一个字符 $x$ ，然后把 $x$ 从这个区间中删除，直到区间为空。你要维护一个集合 $S$ 。

如果 $S$ 为空，你 rp 减 $1$ 。
如果 $S$ 中有一个元素不小于 $x$ ，则你 rp 减 $1$ ，清空 $S$ 。
之后将 x 插入 S。

初始 rp 为 $0$ ，求每次询问搞完一段区间的字符之后最多还有多少 rp。

题目解析

这道题的本质是寻找一个最优的取数策略，使得 rp 减少的次数最少。

第一次取数，S 必为空，rp 必定 -1。
为了避免之后 rp--，我们需要保证每次取数 x 时，S 不为空，且 S 中所有元素都小于 x。这意味着我们要尽可能地按照数值递增的顺序取数。
如果区间内所有数都不同，我们可以严格按照从小到大的顺序取数。除第一次外，不会再有 rp--，最终答案为 -1。

问题出现在有重复数字时。假设我们取了一个数 v，S 中包含了 v。下一次再取 v 时，会满足 S 中有一个元素(v)不小于(>=)当前取的数(v)，导致 rp-- 并且 S 被清空。

设想我们有 k 个"空位"可以放置递增序列。每次取出一个数 x，我们尝试将它放到一个序列的末尾，该序列的末尾元素必须小于 x。如果所有 $k$ 个序列的末尾元素都 >=x，我们就不得不新开一个序列，这对应着一次 rp-- 和 S 的清空。
这个问题等价于：最少需要多少个单调递增子序列才能覆盖区间内所有的数。

根据 Dilworth 定理的对偶定理 Mirsky’s theorem，一个序列能被划分成最少 $k$ 个单调递增子序列，等价于这个序列中最长不增（即下降）子序列的长度为 $k$ 。对于一个可重集，这个结论推广为：最少需要 $k$ 个单调递增序列来覆盖，其中 k 是出现次数最多的那个数（众数）的出现次数。

因此，rp 减少的次数，就是区间内众数的出现次数。
最终答案就是 - (区间众数的出现次数)。

问题转化为一个经典的莫队问题：区间求众数。
我们需要在莫队移动窗口时，高效地维护众数的出现次数。

cnt[v]: 记录值 v 的出现次数。
count_of_counts[k]: 记录出现次数为 k 的数有多少个。
max_freq: 记录当前区间的最大出现次数。

add(x) 操作（将 a[x] 加入区间）:

设 val = a[x]。
count_of_counts[cnt[val]]--：出现次数为 cnt[val] 的数少了一个。
cnt[val]++：val 的出现次数增加。
count_of_counts[cnt[val]]++：出现次数为 cnt[val] (新) 的数多了一个。
如果新的 cnt[val] 大于 max_freq，则更新 max_freq = cnt[val]。

del(x) 操作（将 a[x] 从区间删除）:

设 val = a[x]。
如果 count_of_counts[cnt[val]] 减为 1 后等于 0，并且 cnt[val] 等于当前的 max_freq，这意味着区间内最后一个出现次数为 max_freq 的数被移除了，所以 max_freq 需要减一。
count_of_counts[cnt[val]]--。
cnt[val]--。
count_of_counts[cnt[val]]++。

由于数值范围很大 (10^9)，需要先对所有数进行离散化。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)const int N = 2e5 + 10;
int a[N];
int belong[N];
int B;
int n, m;
int cnt[N]; // 离散化后值的出现次数
int count_of_counts[N]; // 出现次数的计数
int max_freq = 0;struct Query {int l, r, index, ans;
};void add(int x) {int val = a[x];if (cnt[val] > 0) {count_of_counts[cnt[val]]--;}cnt[val]++;count_of_counts[cnt[val]]++;if (cnt[val] > max_freq) {max_freq = cnt[val];}
}void del(int x) {int val = a[x];count_of_counts[cnt[val]]--;if (count_of_counts[cnt[val]] == 0 && cnt[val] == max_freq) {max_freq--;}cnt[val]--;if (cnt[val] > 0) {count_of_counts[cnt[val]]++;}
}void solve() {cin >> n >> m;vector<int> b;for (int i = 1; i <= n; i++) {cin >> a[i];b.push_back(a[i]);}// 离散化sort(b.begin(), b.end());b.erase(unique(b.begin(), b.end()), b.end());for (int i = 1; i <= n; i++) {a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();}B = sqrt(n);vector<Query> q(m);for (int i = 0; i < m; i++) {cin >> q[i].l >> q[i].r;q[i].index = i;belong[q[i].l] = (q[i].l - 1) / B + 1;}sort(q.begin(), q.end(), [&](const Query &x, const Query &y) {int block_x = (x.l - 1) / B;int block_y = (y.l - 1) / B;if (block_x != block_y) return block_x < block_y;if (block_x % 2) return x.r < y.r;return x.r > y.r;});int L = 1, R = 0;for (int i = 0; i < m; i++) {int ql = q[i].l;int qr = q[i].r;while (L > ql) add(--L);while (R < qr) add(++R);while (L < ql) del(L++);while (R > qr) del(R--);q[i].ans = -max_freq;}sort(q.begin(), q.end(), [&](const Query &x, const Query &y) {return x.index < y.index;});for (int i = 0; i < m; i++) {cout << q[i].ans << endl;}
}int main() {close;solve();return 0;
}

P4396 [AHOI2013] 作业 - 洛谷

P4396 [AHOI2013] 作业

题目描述

给定了一个长度为 n 的数列和若干个询问，每个询问是关于数列的区间 [l, r]。你需要统计：

该区间内大于等于 $a$ ，小于等于 $b$ 的数的个数。
该区间内大于等于a，小于等于 b 的，且在该区间中出现过的数值的种类数。

题目解析

这道题是莫队算法与其他数据结构结合的经典例子。外层是莫队算法处理区间 $[l, r]$ 的移动，内层需要一个数据结构来快速回答关于值域 $[a, b]$ 的查询。

外层莫队: 对询问的区间 [l,r] 进行分块排序。维护一个 cnt 数组，cnt[v] 表示当前窗口内数值 v 的出现次数。
内层数据结构: 在莫队的 add/del 操作更新 cnt 数组后，我们需要快速查询。

值域分块:

将值域 [1, 10^5] 分成 sqrt{10^5} 个块。
维护两个数组来支持查询：
- block_sum[i]: 第 i 个块内所有数的总出现次数（对应问题1）。
- block_distinct[i]: 第 i 个块内出现次数大于0的数值种类数（对应问题2）。

莫队 add(x) 操作 (将值 val = a[x] 加入窗口):

cnt[val]++。
block_sum[belong_val[val]]++ (其中 belong_val 是值域分块的归属)。
如果 cnt[val] 从 0 变为 1，说明出现了一个新的数值，block_distinct[belong_val[val]]++。

莫队 del(x) 操作 (将值 val = a[x] 从窗口删除):

cnt[val]--。
block_sum[belong_val[val]]--。
如果 cnt[val] 从 1 变为 0，说明这个数值在窗口内消失了，block_distinct[belong_val[val]]--。

查询 query(a, b):

对于 a 和 b 所在的零散块，暴力遍历 cnt 数组统计答案。
对于 a 和 b 之间的完整块，直接累加 block_sum 和 block_distinct 的值。

这种 莫队 + 值域分块 的方法，总时间复杂度为 $O(n\sqrt{n} + m\sqrt{10^5})$ ，可以通过本题。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)const int N = 1e5 + 10;
int n, m;
int a[N];// 莫队部分
int B_mo;
int belong_mo[N];// 值域分块部分
int B_val;
int belong_val[N];
int val_cnt[N];          // cnt数组
int block_sum[400];      // 对应问题1
int block_distinct[400]; // 对应问题2struct Query {int l, r, a, b, index;
};pair<int, int> ans[N];void add(int x) {int val = a[x];int block_idx = belong_val[val];if (val_cnt[val] == 0) {block_distinct[block_idx]++;}val_cnt[val]++;block_sum[block_idx]++;
}void del(int x) {int val = a[x];int block_idx = belong_val[val];val_cnt[val]--;block_sum[block_idx]--;if (val_cnt[val] == 0) {block_distinct[block_idx]--;}
}pair<int, int> query(int q_a, int q_b) {int res1 = 0, res2 = 0;int block_a = belong_val[q_a];int block_b = belong_val[q_b];if (block_a == block_b) {for (int i = q_a; i <= q_b; i++) {res1 += val_cnt[i];if (val_cnt[i] > 0) res2++;}} else {// 处理左边散块int R_a = block_a * B_val;for (int i = q_a; i <= R_a; i++) {res1 += val_cnt[i];if (val_cnt[i] > 0) res2++;}// 处理中间整块for (int i = block_a + 1; i < block_b; i++) {res1 += block_sum[i];res2 += block_distinct[i];}// 处理右边散块int L_b = (block_b - 1) * B_val + 1;for (int i = L_b; i <= q_b; i++) {res1 += val_cnt[i];if (val_cnt[i] > 0) res2++;}}return {res1, res2};
}void solve() {cin >> n >> m;int max_val = 0;for (int i = 1; i <= n; i++) {cin >> a[i];max_val = max(max_val, a[i]);}B_mo = sqrt(n);for(int i = 1; i <= n; i++) {belong_mo[i] = (i - 1) / B_mo + 1;}B_val = sqrt(max_val);for(int i = 1; i <= max_val; i++) {belong_val[i] = (i - 1) / B_val + 1;}vector<Query> queries(m);for (int i = 0; i < m; i++) {cin >> queries[i].l >> queries[i].r >> queries[i].a >> queries[i].b;queries[i].index = i;}sort(queries.begin(), queries.end(), [&](const Query &x, const Query &y) {if (belong_mo[x.l] != belong_mo[y.l]) return belong_mo[x.l] < belong_mo[y.l];if (belong_mo[x.l] % 2) return x.r < y.r;return x.r > y.r;});int L = 1, R = 0;for (int i = 0; i < m; i++) {while (L > queries[i].l) add(--L);while (R < queries[i].r) add(++R);while (L < queries[i].l) del(L++);while (R > queries[i].r) del(R--);ans[queries[i].index] = query(queries[i].a, queries[i].b);}for (int i = 0; i < m; i++) {cout << ans[i].first << " " << ans[i].second << endl;}
}int main() {close;solve();return 0;
}

P3674 小清新人渣的本愿 - 洛谷

P3674 小清新人渣的本愿

题目描述

给你一个序列 a，有 m 次操作，每次询问一个区间是否可以选出两个数它们的差为 x，或者和为 x，或者乘积为 x。选出的这两个数可以是同一个位置的数。

题目解析

这道题是莫队算法与 bitset 优化的结合。bitset 是一种空间和时间常数都极小的位运算数据结构，非常适合处理 “是否存在” 这类布尔性质的问题。

我们使用莫队来处理区间查询。在莫队维护的窗口内，我们用一个 bitset 来记录哪些数值是存在的。

cnt[v]: 记录数值 v 在当前窗口的出现次数。
bitset<N> s: s[v] = 1 表示数值 v 存在于当前窗口，否则 s[v] = 0。

add(x) / del(x):

add: cnt[a[x]]++。如果 cnt[a[x]] 从 0 变为 1，则 s[a[x]] = 1。
del: cnt[a[x]]--。如果 cnt[a[x]] 从 1 变为 0，则 s[a[x]] = 0。

对于三种查询操作：

差为 x (a - b = x): 是否存在两个数 p, q 使得 p - q = x，即 p = q + x。
这等价于询问是否存在一个 q，使得 s[q] 和 s[q+x] 同时为 1。
我们可以用 bitset 的位运算来检查：s & (s << x)。如果这个结果不全为 0，即 (s & (s << x)).any() 为 true，则存在这样的数对。s << x 将 s 的每一位向左移动 x 位，原来的第 q 位移动到第 q+x 位。与原 s 取 & 操作，如果结果的某一位为 1，说明 s[q+x] 和 s[q] 都为 1。
和为 x (a + b = x): 是否存在两个数 p, q 使得 p + q = x，即 p = x - q。
这等价于询问是否存在一个 q，使得 s[q] 和 s[x-q] 同时为 1。
直接用 bitset 难以实现。但我们可以预处理一个反转的 bitset。
- s_rev[v] = s[MAX_VAL - v]
- s[x-q] 存在 s_rev[MAX_VAL - (x-q)] 存在 s_rev[MAX_VAL - x + q] 存在。
- 检查 s 和 s 的某种变换后的 &。s 中有 q，s_rev 移位后对应位置要有 x-q。
- s_rev >> (MAX_VAL - x) 会将 s_rev 的 MAX_VAL - x + q 位移动到第 q 位。
- 所以，我们检查 (s & (s_rev >> (MAX_VAL - x))).any() 即可。
积为 x (a * b = x): bitset 对乘法无能为力。但由于数值 x 不超过 $10^5$ ，我们可以暴力枚举 x 的所有因子。
- 遍历 i 从 1 到 sqrt{x}。
- 如果 i 是 x 的因子，就检查 s[i] 和 s[x/i] 是否都为 1。
- 如果找到一对，则存在，查询结束。

这个方法结合了莫队、bitset 和数论知识，可以在时限内解决问题。

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)const int N = 1e5 + 1;
int a[N];
int belong[N];
int cnt[N];
bitset<N> s, s_rev;
int B;
int n, m;struct Query {int op, l, r, x, index;bool ans;
};void add(int x) {int val = a[x];if (cnt[val] == 0) {s[val] = 1;s_rev[N - 1 - val] = 1;}cnt[val]++;
}void del(int x) {int val = a[x];cnt[val]--;if (cnt[val] == 0) {s[val] = 0;s_rev[N - 1 - val] = 0;}
}void solve() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];B = sqrt(n);for (int i = 1; i <= n; i++) belong[i] = (i - 1) / B + 1;vector<Query> q(m);for (int i = 0; i < m; i++) {cin >> q[i].op >> q[i].l >> q[i].r >> q[i].x;q[i].index = i;}sort(q.begin(), q.end(), [&](const Query &x, const Query &y) {if (belong[x.l] != belong[y.l]) return belong[x.l] < belong[y.l];if (belong[x.l] % 2) return x.r < y.r;return x.r > y.r;});int L = 1, R = 0;for (int i = 0; i < m; i++) {int ql = q[i].l, qr = q[i].r, qx = q[i].x;while (L > ql) add(--L);while (R < qr) add(++R);while (L < ql) del(L++);while (R > qr) del(R--);if (q[i].op == 1) {if ((s & (s << qx)).any()) {q[i].ans = true;}} else if (q[i].op == 2) {if (qx < N) {if ((s & (s_rev >> (N - 1 - qx))).any()) {q[i].ans = true;}}} else {for (int j = 1; j * j <= qx; j++) {if (qx % j == 0) {if (s[j] && s[qx / j]) {q[i].ans = true;break;}}}}}sort(q.begin(), q.end(), [&](const Query &x, const Query &y) {return x.index < y.index;});for (int i = 0; i < m; i++) {if (q[i].ans) {cout << "hana" << endl;} else {cout << "bi" << endl;}}
}int main() {close;solve();return 0;
}