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

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

莫队初步部分题解：

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

P2709 小B的询问

题目描述

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

$$\sum _{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。

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

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

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

1. 从总答案中减去旧的贡献：ans -= cnt[val] * cnt[val]
2. 更新该值的出现次数：cnt[val]--
3. 向总答案中加入新的贡献：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 只袜子中随机取两只，总方案数是组合数
  $$\left(\genfrac{}{}{0ex}{}{\text{len}}{2}\right)=\frac{\text{len}\times (\text{len}-1)}{2}$$
  。

• 设颜色 i 在区间内出现了 c_i 次。从中取出两只颜色为 i 的袜子的方案数是
  $$\left(\genfrac{}{}{0ex}{}{c_i}{2}\right)=\frac{c_i\times (c_i-1)}{2}$$
  。

• 因此，取出两只颜色相同袜子的总方案数是
  $$\sum \left(\genfrac{}{}{0ex}{}{c_i}{2}\right)$$
  。

• 概率
  $$P=\frac{\sum \left(\genfrac{}{}{0ex}{}{c_i}{2}\right)}{\left(\genfrac{}{}{0ex}{}{\text{len}}{2}\right)}=\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。所以公式可以化为
  $$P=\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。

题目解析

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

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

问题转化为：对于一个查询 [l, r]，我们需要统计满足
$$l\le x\le y\le r$$
且
$$s[x-1]=s[y]\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] 加入区间）:

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

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

1. 设 val = a[x]。
2. 如果 count_of_counts[cnt[val]] 减为 1 后等于 0，并且 cnt[val] 等于当前的 max_freq，这意味着区间内最后一个出现次数为 max_freq 的数被移除了，所以 max_freq 需要减一。
3. count_of_counts[cnt[val]]--。
4. cnt[val]--。
5. 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]。你需要统计：

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

题目解析

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

• 外层莫队: 对询问的区间 [l,r] 进行分块排序。维护一个 cnt 数组，cnt[v] 表示当前窗口内数值 v 的出现次数。

• 内层数据结构: 在莫队的 add/del 操作更新 cnt 数组后，我们需要快速查询。

值域分块:

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

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

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

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

1. cnt[val]--。
2. block_sum[belong_val[val]]--。
3. 如果 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]; // 对应问题2

struct 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。

对于三种查询操作：

1. 差为 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。

2. 和为 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() 即可。

3. 积为 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;
}