# 契约召唤 题解

解法署名：可达闭包与三维支配查询来自出题人解法；Codex（GPT-6）采用按桶大小建立的静态范围树，并给出空间上界与正确性证明。

## 解法比较

### 出题人解法：树状数组套动态线段树

出题人解法用队列逐个处理可用角色，求所有可召唤 NPC 的闭包；每次检索都是对同一角色的三维支配查询。将三维需求离散化后，第一维用树状数组：一个 NPC 加入若干树状数组桶，查询第一维前缀时访问互不相交的若干桶。

每个桶在全局第二维排名范围上动态建立线段树。一个叶子对应一个第二维排名，保存按第三维需求排序的 NPC 列表和尚未处理的位置；内部节点保存剩余第三维需求的最小值。查询第二维前缀时，跳过最小值大于角色第三维属性的子树，取出符合要求的叶子列表前缀并推进指针，再更新最小值。每个副本只被取出一次，全局访问标记防止同一 NPC 重复入队。

第一维桶划分和第二维前缀只保留满足前两项条件的对象，最小值和有序列表精确检查第三项；首次取出副本即入队，延迟处理其他副本不会漏掉未发现的 NPC。下文的闭包证明同样适用于出题人解法。

每个 NPC 有 $O(\log(n+1))$ 份副本，桶内查询及更新沿线段树路径进行，出题人解法总时间为 $O(n\log^2(n+1))$ .但每个副本可能在全局第二维值域中创建 $O(\log(n+1))$ 个动态节点，空间上界为 $O(n\log^2(n+1))$ ；出题人实现按这一上界预留节点池。

### Codex 采用的静态范围树方案

Codex 实现的第一维使用静态线段树，并将每个桶内的副本按第二维排序，只在**该桶实际拥有的副本**上建立紧凑的最小值线段树。大小为 $s$ 的桶只需 $O(s)$ 空间，所有桶合计为 $O(n\log(n+1))$ .这消除了动态内层树按全局值域开路径的额外对数空间因子；总时间仍为 $O(n\log^2(n+1))$ .

闭包、三维支配查询及通过访问标记抑制重复均来自出题人解法。静态范围树的优势是可证明的空间上界与按实际桶大小分配的存储；它仍保存多个副本并维护内层树。这里比较的是理论界，没有两种实现的直接计时或峰值内存对照。

## 召唤就是可达闭包

队列初始只含召唤师。取出一个可用角色，找出需求三元组逐项不超过它的属性三元组的 NPC，将尚未加入过的 NPC 入队。每种 NPC 只入队一次。

不会消耗角色或改变属性，所以任何已经可行的召唤始终可行。每次入队都有实际召唤依据；反过来，任何可达 NPC 的直接召唤者最终都会出队，因此不会漏掉它。

不能把所有可用角色的三个属性分别取最大值：这可能把不同角色的能力拼成一个实际不存在的召唤者。

## 第一维的前缀分解

将所有 NPC 按第一维需求排序，以排序位置建一棵静态线段树。每个 NPC 在从其叶子到根的所有节点中各保存一个副本，共 $O(\log(n+1))$ 份。

对属性为 $(F,I,S)$ 的角色，第一维需求不超过 $F$ 的所有位置是一个前缀。用线段树将该前缀分解为 $O(\log(n+1))$ 个互不相交的完整节点，只查询这些节点的桶。

## 桶内检索第二、三维

每个桶中的 NPC 按第二维需求排序，并建立另一棵线段树，在叶子存第三维需求，在内部存最小值。

先二分第二维不超过 $I$ 的前缀终点，再在这个前缀中寻找第三维不超过 $S$ 的叶子。搜索遇到区间越过前缀或区间最小值大于 $S$ 时跳过；否则向孩子下降，找到一个符合条件的 NPC。

找到后，把**当前桶中这个副本**的第三维改为无穷大，并向上更新最小值。如果 NPC 尚未访问，则标记并加入召唤队列；已经访问的 NPC 不重复入队。继续搜索这个桶，直到没有候选。

无需立即在所有其他桶中删除同一 NPC 的副本：它们以后遇到时再删除，访问标记可以避免重复召唤。每个副本最多被删除一次。

## 正确性与复杂度

第一维分解覆盖且仅覆盖满足力量要求的 NPC，桶内前缀覆盖且仅覆盖满足智力要求的副本，最小值搜索精确筛选精神要求。所以每次找到的对象满足全部三项条件。

尚未召唤的 NPC 不可能有被删除的副本：第一次删除它的任意副本时就会使它入队。因此延迟删除其他副本不会漏掉任何尚未发现的 NPC。结合闭包过程的证明，最终计数正确。

预处理先按第二维全局排序，再把 NPC 沿第一维祖先链插入各桶，使每个桶自然有序；各桶最小值线段树的总大小为 $O(n\log(n+1))$ .

每个可用角色访问 $O(\log(n+1))$ 个桶。桶内一次前缀查找或删除耗时 $O(\log(n+1))$ ；总共只有 $O(n\log(n+1))$ 份副本可以被删除。角色至多有 $n+1$ 个，所以总时间为 $O(n\log^2(n+1))$ ，空间为 $O(n\log(n+1))$ .这不依赖随机平衡或启发式剪枝。

无穷大取严格大于所有合法属性的数。重复需求保留为不同叶子，因为题目按 NPC 种类计数。

## 验证

独立模型逐个角色扫描全部 NPC，直接计算可达闭包。专门覆盖属性不能合并、需求相等、零属性、重复 NPC、无人可召唤和反序长链；正式规模包含一次报告全部 NPC 的情形。

性能测量见[评测环境与性能](../../../docs/评测环境与性能.md)。