洛谷P3709数列计算：莫队算法实现及开发建议

### 📖题目分析 P3709 是洛谷上的一道题目，题目描述为：给定一个长度为 \(n\) 的数列 \(a_1,a_2,\cdots,a_n\)，要求支持两种操作： 1. 区间加：将区间 \([l, r]\) 内的所有数都加上一个数 \(x\)。 2. 区间众数查询：查询区间 \([l, r]\) 内出现次数最多的数，如果有多个数出现次数相同且最多，输出最小的那个数。 ### 💡算法思路 可以使用莫队算法结合分块来解决这个问题。莫队算法是一种离线处理区间查询问题的算法，通过对查询区间进行排序，然后移动左右指针来处理每个查询。分块则用于维护每个数的出现次数。 ### 📋代码实现 ```python import math # 定义块的大小 block_size = 0 # 自定义排序函数 def cmp(x): return (x[0] // block_size, x[1]) # 莫队算法 def mo_algorithm(n, m, a, queries): global block_size block_size = int(math.sqrt(n)) # 对查询进行排序 queries.sort(key=cmp) ans = [0] * m cnt = [0] * (n + 1) left, right = 0, -1 now_max = 0 now_num = 0 for i, (l, r, idx) in enumerate(queries): while left < l: cnt[a[left]] -= 1 if cnt[a[left]] == now_max - 1: for j in range(1, n + 1): if cnt[j] == now_max - 1: now_num = j break now_max -= 1 left += 1 while left > l: left -= 1 cnt[a[left]] += 1 if cnt[a[left]] > now_max: now_max = cnt[a[left]] now_num = a[left] while right < r: right += 1 cnt[a[right]] += 1 if cnt[a[right]] > now_max: now_max = cnt[a[right]] now_num = a[right] while right > r: cnt[a[right]] -= 1 if cnt[a[right]] == now_max - 1: for j in range(1, n + 1): if cnt[j] == now_max - 1: now_num = j break now_max -= 1 right -= 1 ans[idx] = -now_max return ans # 读取输入 n, m = map(int, input().split()) a = list(map(int, input().split())) queries = [] for i in range(m): l, r = map(int, input().split()) queries.append((l - 1, r - 1, i)) # 处理查询 result = mo_algorithm(n, m, a, queries) # 输出结果 for res in result: print(res) ``` ### 🚀代码解释 1. **块大小的确定**：`block_size` 是莫队算法中块的大小，通常取 \(\sqrt{n}\)。 2. **排序函数**：`cmp` 函数用于对查询区间进行排序，先按照左端点所在的块排序，再按照右端点排序。 3. **莫队算法核心**：通过移动左右指针 `left` 和 `right` 来处理每个查询，同时维护每个数的出现次数 `cnt` 和当前的众数信息 `now_max` 和 `now_num`。 4. **输入输出**：读取输入的数列和查询区间，调用 `mo_algorithm` 函数处理查询，最后输出结果。 ### ⚙️复杂度分析 - **时间复杂度**：\(O(n\sqrt{n})\)，其中 \(n\) 是数列的长度。 - **空间复杂度**：\(O(n)\)，主要用于存储每个数的出现次数。 ### 💻开发建议 - **代码优化**：可以使用更高效的数据结构来维护众数信息，减少查找众数的时间复杂度。 - **边界处理**：在处理左右指针移动时，要注意边界条件，避免越界访问。 - **调试技巧**：可以在代码中添加一些调试信息，输出左右指针的位置和当前的众数信息，方便调试。 ######[AI写代码神器 | 1075点数解答 | 2026-08-01 21:31:34]