20250802双周赛记录

20250802双周赛记录

这次双周赛值得记录的就是两个题目 一个题目是贪心（较为简单），另外一个就是回滚莫队算法（难度很高，可以先看下莫队算法）

最早玩车工陆地和水上游乐设施的时间

给你两种类别的游乐园项目：陆地游乐设施 和 水上游乐设施。

• 陆地游乐设施
  • landStartTime[i] – 第 i 个陆地游乐设施最早可以开始的时间。
  • landDuration[i] – 第 i 个陆地游乐设施持续的时间。
• 水上游乐设施
  • waterStartTime[j] – 第 j 个水上游乐设施最早可以开始的时间。
  • waterDuration[j] – 第 j 个水上游乐设施持续的时间。

一位游客必须从 每个 类别中体验 恰好****一个 游乐设施，顺序 不限 。

• 游乐设施可以在其开放时间开始，或 之后任意时间 开始。
• 如果一个游乐设施在时间 t 开始，它将在时间 t + duration 结束。
• 完成一个游乐设施后，游客可以立即乘坐另一个（如果它已经开放），或者等待它开放。

返回游客完成这两个游乐设施的 最早可能时间 。

提示:

• 1 <= n, m <= 5 * 10^4
• landStartTime.length == landDuration.length == n
• waterStartTime.length == waterDuration.length == m
• 1 <= landStartTime[i], landDuration[i], waterStartTime[j], waterDuration[j] <= 10^5

题解：

这是第三题数据范围大了点，第二题数据范围是10^2，那么这样其实就可以做一个二层的嵌套循环就可以实现了，每次只要对两个排序后的数组，只用遍历两个乐园就可以得到结果了。

可以总结成一个贪心问题，最优化需要满足以下问题：

• 不论是怎么样都分为两个条件，第一个条件是先玩水项目，第二个条件是先玩陆地项目。
• 假设我们先玩的水上项目，如果我们的后面的陆地项目固定了（假设），那么我们肯定是希望可以找到水上项目结束时间最靠前的，因为后面的项目的开始时间一定是根据水上项目的结束时间来定的。
• 假设先玩的是陆地项目，那么同理。

所以我们只需要找到先玩项目最短的结束时间 然后遍历后面的项目就好了。

---

查询超过阈值频率最高元素

给你一个长度为 n 的整数数组 nums 和一个查询数组 queries，其中 queries[i] = [li, ri, thresholdi]。返回一个整数数组 ans，其中 ans[i] 等于子数组 nums[li...ri] 中出现 至少 thresholdi 次的元素，选择频率 最高 的元素（如果频率相同则选择 最小 的元素），如果不存在这样的元素则返回 -1。

提示：

• 1 <= nums.length == n <= 104
• 1 <= nums[i] <= 109
• 1 <= queries.length <= 5 * 104
• queries[i] = [li, ri, thresholdi]
• 0 <= li <= ri < n
• 1 <= thresholdi <= ri - li + 1

题解：

题目理解

给定数组 nums 和查询数组 queries，每个查询包含 [l, r, threshold]，要求找到区间 [l, r] 中：

• 出现次数 ≥ threshold 的元素
• 在满足条件的元素中，选择出现次数最多的
• 如果出现次数相同，选择数值最小的
• 如果没有满足条件的元素，返回 -1

方法一：暴力解法

思路

对每个查询直接遍历区间，统计每个元素的出现次数，找到满足条件的答案。

实现要点

复杂度分析

• 时间复杂度：O(q × n)，每个查询需要 O(n) 时间遍历区间
• 空间复杂度：O(n)，哈希表存储元素计数

方法二：传统莫队算法

思路

将查询按照 (l // B, r) 排序（B = √n），通过维护一个滑动窗口来回答所有查询。

主要挑战

传统莫队需要支持：

• 添加元素：容易实现，更新计数和最大频率
• 删除元素：困难！删除一个最大频率的元素后，如何快速找到新的最大频率？

解决删除操作的方法

1. 有序集合：维护 (频率, 元素值) 的有序结构
2. 懒删除堆：使用堆维护最大频率，配合懒删除机制
3. 频率桶：为每个频率维护一个集合

这些方法都会增加实现复杂度和常数因子。

复杂度分析

• 时间复杂度：O((n+q)√n × log n)，额外的 log n 来自有序结构
• 空间复杂度：O(n)

方法三：回滚莫队算法 ⭐

核心思想

避免删除操作！设计一种只需要添加元素的算法流程。

详细思路

1. 查询分类

• 短查询（长度 ≤ √n）：直接暴力处理
• 长查询（长度 > √n）：使用回滚莫队（左端点和右端点绝对不再一个块内）

2. 分块处理

• 将数组按 √n 大小分块
• 将长查询按左端点所在块分组
• 每组内按右端点递增排序

3. 回滚莫队执行流程

对于每个块内的查询：（这里的块的右端点 指的是根据左端点所在的那个块的最右边 查询的右端点 指的是 根据左端点分组的查询 对应的右端点）

全局状态：
- cnt: 元素出现次数的哈希表
- maxCnt: 当前最大出现次数
- minVal: 最大出现次数对应的最小元素

处理块内查询的流程：
1. 右端点扩展（持久操作，扩展到下一个查询的右端点 一直加）
   - 从上一个查询的右端点继续向右移动到当前查询的右端点
   - 每移动一步就添加一个元素，更新 cnt, maxCnt, minVal

2. 保存状态（回滚点 这个时候左端点是在块间隔也就是当前块的右端点）
   - saved_maxCnt = maxCnt
   - saved_minVal = minVal

3. 左端点扩展（临时操作 每一次扩展左端点都是块的右边界向左扩展 添加）
   - 从块的右边界向左移动到查询的左端点
   - 继续添加元素，更新 cnt, maxCnt, minVal

4. 计算答案
   - answer = minVal if maxCnt >= threshold else -1

5. 状态回滚（关键！左端点回滚到块的右端点 并且状态回滚到保存点 继续扩展右端点到下一个查询的右端点）
   - maxCnt = saved_maxCnt
   - minVal = saved_minVal
   - 注意：cnt 保持不变，仍包含右端点扩展的所有元素

4. 块间切换

当处理完一个块，切换到下一个块时：

• 完全重置所有状态：cnt = {}, maxCnt = 0, minVal = ∞
• 重置右端点到新块的右边界

为什么回滚可行？

• cnt 维护从块右边界+1到当前右端点的累积计数
• 统计信息可以回滚，相当于”忘记”左端点扩展的影响
• 下次查询时，左端点重新从块边界开始扩展

复杂度分析

设块大小 B = √n，共有 √n 个块。

短查询复杂度：

• 每个短查询：O(B) = O(√n)
• 最多 q 个短查询：O(q√n)

长查询复杂度：

1. 块间切换：√n 个块，每次切换 O(1)，总计 O(√n)
2. 右端点移动：
   • 每个块内右端点单调递增
   • 所有块的右端点移动总和：O(n√n)
3. 左端点移动：
   • 每个查询的左端点最多移动 √n 步
   • 所有长查询的左端点移动：O(q√n)

总时间复杂度： O(q√n + √n + n√n + q√n) = O((n+q)√n)