几何、扫描线、模拟与解析 · HTML
数学 / 逻辑形态
给定 API 操作集与时间界；为每个操作列所需查询/修改，选择互补结构，并规定所有副本同步更新。
识别信号
- 要求实现一个类或在线 API
- 不同操作需要不同访问方向
- 目标复杂度明确
- 单一容器无法同时满足全部操作
- 需维护缓存、集合、迭代或排名
容易误判的相似信号
| Signal | Why it is different |
|---|
| 离线一次性计算 | 若所有操作预先可见，排序或批处理可能更简单，无需复杂在线结构。 |
| 过度复制状态 | 每多一份派生数据就多一条同步义务，容易出现幽灵条目。 |
核心不变量
每个逻辑元素在所有索引中的表示一致；主存储决定真值，辅助索引只加速访问且可由主状态验证。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 按操作需求选择数组、哈希、堆、链表等；示例 IndexedSet 用 items 与 pos 双向对应。 |
| Transition | 每个公开操作先检查前置条件，再以不破坏中间引用的顺序原子更新所有结构。 |
| Frontier / order | 无遍历前沿；API 调用边界是事务边界，返回前必须恢复完整不变量。 |
Python 骨架
class IndexedSet:
def __init__(self):
self.items = []
self.pos = {}
def add(self, value):
if value in self.pos: return False
self.pos[value] = len(self.items)
self.items.append(value)
return True
def remove(self, value):
if value not in self.pos: return False
i = self.pos.pop(value)
last = self.items.pop()
if i < len(self.items):
self.items[i] = last
self.pos[last] = i
return True
def contains(self, value):
return value in self.pos
def at(self, index):
return self.items[index]
正确性思路
- 初始数组与映射都空，双向对应成立。
- add 把新值放在末尾并记录该位置。
- remove 用末元素填洞，并同步更新被移动值的位置。
- 其余元素位置不变，因此每次 API 返回前不变量恢复。
复杂度
| Time | Space | Parameters |
|---|
| add/remove/contains 摊还 O(1)，at O(1) | O(n) | n 为当前元素数；依赖哈希表摊还界 |
边界条件
- 重复 add
- 删除不存在元素
- 删除恰好末元素
- 空结构 at 越界
- 可变对象不可直接作为稳定哈希键
错误模式
| Pattern | Why it fails / fix |
|---|
| 填洞后漏改索引 | 移动的末元素会保留旧位置。 |
| 先 pop 数组再读取末值 | 更新顺序必须保留所有待用信息。 |
| 只测返回值不测不变量 | 应在随机操作序列后核对 pos 与 items 双向一致。 |
选择与排除规则
- 先写 API 与复杂度表，再选结构。
- 为每份冗余状态写同步责任。
- 删除数组中间元素想 O(1) 且无序：末元素填洞。
- 需要稳定顺序时不能使用填洞，改用链表或树。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 数组可变为 [a,c]，映射为 a→0、c→1。 |
| Scenario | IndexedSet 中依次加入 a、b、c，再删除 b。 |
| Walkthrough | 取末元素 c 填入 b 的洞，再把 c 的索引从 2 更新为 1。 |
Recall prompts
我的补充