“利用有序划分精化，用一个块保存同标签顶点，块按标签从大到小排列。取第一块里的元素作为v；移除v，再用v的未选邻居精化所有触及块。每块的邻居交集在前，非邻居余集在后。初始化只有一个全体顶点块，…”
形式陈述
块有先后，块内元素没有优先级
设初始元素为整数0,…,n−1，当前仍活动的元素集合为U。有序划分是非空块的序列
操作 refine(S) 接受活动元素的可枚举列表，重复元素按第一次出现处理；令S也表示这些元素组成的集合。它把每个原块B原位替换为
略去空块。不同原块的相对次序保持不变。操作 pop_first() 从最前一块取出一个元素并使其退出U；该块变空时一起移除。空划分上的取出操作报错，空列表精化则不改变状态。
这是一种按给定集合逐步区分元素的维护方法，不会自行计算S，也不会合并过去已分开的块。以下实现给定n个连续整数身份；若外部对象是字符串，需要先付出建表和编码成本。[1, PDF pp.14–16；2]
直觉
为什么只看S，就能知道哪些块要分裂
若B∩S为空，B完全不动。若非空，总能在遍历S时遇到其中一个元素；该元素保存的owner指针直接给出B。因而无须从头检查每个块，更不必扫描B里那些不在S的元素。
每个元素保存prev、next和owner。每个块保存首尾元素、大小及前后块指针。块链与块内链都采用可凭节点身份局部修改的双向链表：从已知块摘下已知元素、在已知块前插入新块、删除已知空块，都只改常数个引用。只知道元素值、还需要顺链搜索它的实现，不具备这个成本条件。
一轮中，一个旧块只创建一个新块
给每次精化一个递增轮号epoch，并为元素保存本轮是否已处理的标记。第一次遇到原块B中的元素时，在B前创建一个空块T，记录B.target=T及B.epoch=epoch。随后遇到同一原块的元素，都移动到同一个T，不再创建块。
移动时先修改原块相邻元素的链接，再把该元素接到T尾部，并令owner指向T。新块内的元素按本轮输入首次出现的顺序排列；原余块中的元素保持原链相对顺序。这个并列规则可以重放，却不等同于“始终选最小编号”。
轮末只遍历本轮触及的原块：清除临时target，移除已经为空的余块。若某个原块被全部选中，它的新交块占据原来位置，空余块消失；抽象划分没有被多分一块。
三条不变量怎样穿过一次移动
轮开始时，每个活动元素恰属于一个非空块；块内链与owner一致；块链依次覆盖整个活动集合。处理一个还没出现的x时，从原块摘下它再接入新块，既不复制也不丢失身份。原块对应的新块始终紧邻并位于它之前，因此不会跨过其他原块。
处理过的元素owner已改变，必须先检查元素轮号，再读取owner并决定是否分裂。否则重复的x会被当成“新块里的另一个待分元素”，把本应一次的精化误做多次。轮末删除空块后，三条不变量恢复成供下一次操作使用的完整形式。
例子与边界
两次精化与一次删除
初始块为 [0,1,2,3,4,5]。输入S=[4,1,4]，4的第二次出现被忽略，结果为 [4,1] | [0,2,3,5]。再输入T=[2,1,5]：第一块分成 [1] | [4]，第二块分成 [2,5] | [0,3]，全局结果为
随后 pop_first() 返回1并删除它的单元素块，剩下 [4] | [2,5] | [0,3]。两次精化都不能把已经分开的4和2重新放进同一块。
不能把所有被选元素集中到最前面
从 [0,1] | [2,3] 按S={1,3}精化，正确结果是 [1] | [0] | [3] | [2]。若改成 [1,3] | [0,2]，不仅合并了旧块，还让原来更靠后的3越过0，丢掉之前已经建立的优先关系。
空U允许零个块。S=U时，各块仍分别保留，而不是合并成一个块。删除后的元素不再是合法精化输入。附件的变更核心对非法编号、非整数或已删除身份立即报错，但不承诺把此前已处理元素回滚；需要事务语义的调用方应先完成输入验证。
历史空块也会占空间
若每次分裂都向一个永不清理的数组追加块，即使当前仅有n个元素，历史块对象也可能随操作次数增长。附件使用可摘除的独立块对象，轮末清除临时引用，删除块时断开前后指针，不保留历史空块表。输出日志若主动保存快照，属于另一份空间预算。
推论与应用
给每个输入项和每个触及块记账
一次精化接收长度s的列表，检查每个输入项一次。不同触及旧块的数量不超过本轮不同元素数，每个触及块只创建一个交块并做一次收尾，所以成本为O(1+s)。即使S为空，调用和轮号更新仍有常数成本。
初始化O(n)，q次精化及p次成功取出，总时间为
这里
稳定状态下，非空块数不超过活动元素数；一轮最多为每个触及旧块临时新增一个交块，块对象仍是O(n)。元素数组、块链和本轮触及列表共O(n)工作空间。枚举一份完整快照需O(n)，连续q份快照可能占O(qn)；它不是核心精化操作免费附带的结果。
从优先级维护走向图搜索
字典序广度优先搜索让S等于刚选顶点的尚未选择邻居。一个块内的顶点拥有相同历史标签；精化把刚得到新标签位的邻居放在该块非邻居之前。每条边只触发一次活动端点移动，因此这份局部数据结构把看似需要反复比较长标签的搜索压到线性时间。
在弦图证书终结任务中，先手算上述两轮精化，再检查实际搜索的块轨迹。验收重点是旧块次序和元素身份都保持，而非只比较最后输出的顶点集合。
参考资料
- David Eppstein，CS 163 & CS 265, Lecture 7a，2026，讲义PDF，物理第14、16页：按邻域精化有序块及对应的数据结构要求。
- Michel Habib、Ross M. McConnell、Christophe Paul、Laurent Viennot，Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing，Theoretical Computer Science 234，2000，59–84，出版信息与摘要。