契约召唤 题解¶
解法署名：可达闭包与三维支配查询来自出题人解法；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 的情形。
性能测量见评测环境与性能。