提交记录：https://qoj.ac/submission/3257840。

AI Disclosure：全是 GPT-6 Astra 干的。

先把题意压缩一下：位置 $i$ 在时刻 $p_i$ 确定颜色，Alice 控制 $a_i=-1$ 的位置，Bob 控制 $a_i=-2$ 的位置，其余位置原本有固定色。Alice 最大化最终最长同色段，Bob 最小化它。$typ=2$ 要求每个实际决策前缀之后，剩余双方最优行动的答案；已执行位置一律使用实际值，包括原固定位置。

这题可以分成三个问题来想：

1. 最后一步决策消掉以后，剩下的局面还能用什么表示？
2. 同时维护所有可能的答案，会不会产生太多状态？
3. 状态确定以后，怎样一边读入实际决策，一边在线求值？

对应的做法是倒序消元、带权条件压缩、单调失效传播。前两部分决定算法的结构，最后再利用 word-RAM，把线性次维护操作的总费用也压到线性。

下面先讲清这些观察，再补齐实现所需的结构。最终在字长 $w=\Theta(\log n)$ 的 word-RAM 上，时间为确定性摊还 $O(n)$，空间为 $O(n)$，支持两种 $typ$ 和强制在线。

1. 从最后一个决策倒着想

直接按时间正序考虑策略，很难概括“这个决策对最终最长段有什么影响”。先固定一个阈值 $k$，只问 Alice 能否保证答案至少为 $k$，局面就简单了：只要某个长度为 $k$ 的窗口同色即可。

于是判定式为 $F_k=\bigvee_I[I\text{ 同色}]$。我们尝试按决策时间倒序，把最后一个变量消掉，并让这个式子仍然长得像“若干区间同色条件的或”。

先去掉没用的条件

倒序过程中，只删除 Alice、Bob 的位置，原固定位置先作为颜色参数保留。一个条件的支持，就是它要求同色的那些剩余位置。支持在剩余序列上连续，原坐标中间可以有已经删除的点。

如果 $I\subseteq J$，那么 $J$ 同色一定会使 $I$ 同色。既然我们只需要某个条件成立，$J$ 就没有存在的必要。

这个方向很重要：在同一个答案阈值下，要求同色的位置越少，条件越有用。 去掉包含关系后，左右端点都严格递增，每个位置至多对应一个左端点、一个右端点。后面的消元能够保持简单，正是因为这种区间反链结构。

Alice 可以直接删，Bob 留下一次左右拼接

设最后一个自由位置为 $x$。

如果它属于 Alice，她只需要选择一个颜色，让某个条件成立。对于一个包含 $x$ 的条件，只要其余位置同色，Alice 就能把 $x$ 补成同色。因此直接从所有支持中删去 $x$ 即可。出现空集或单点时，对应条件已经恒真。

如果它属于 Bob，就要同时应付 $x=0,1$ 两种情况。不含 $x$ 的条件直接保留；若两种情况分别依靠两个含 $x$ 的条件成功，那么删去 $x$ 后，两份支持必须分别全为 $0$、全为 $1$，所以不能再有公共位置。

区间连续，加上每份支持至少有两个点，就只可能是一个结束于 $x$ 的 $[l,x]$，与一个开始于 $x$ 的 $[x,r]$ 配对。

例如，局部状态是 $00\,x\,11$。Bob 填 $0$，左边出现长度 $3$ 的同色段；填 $1$，右边出现长度 $3$ 的同色段。这份保证依赖的条件，恰好是“左边同色、右边同色，且左右异色”。

这时把 $x$ 右侧的整个后缀翻色，左右异色就变成了同色。再删掉 $x$，便得到一个新区间条件。其他存活条件都在 $x$ 的某一侧，整体翻色不改变它们的同色性；自由变量取反后依旧可以自由选色。

从布尔运算看，Alice 对应存在量词，Bob 对应全称量词。一般的量词消元可能把表达式弄得很复杂，而这里“区间连续、公共点只能是 $x$”把新表达式限制成了一次左右拼接。

以后每删一个 Bob，都统一翻转右侧后缀，即使本次没有生成条件。这样所有阈值共用同一套颜色坐标。一个位置累计翻色次数的奇偶性称为它的相位，归一化颜色就是原颜色异或相位。

2. 用一个权值装下所有答案阈值

如果分别对每个 $k$ 做一遍消元，许多完全相同的结构会被重复维护。可以把它们合起来：一个条件附上权值 $h$，表示这个条件成立时，答案至少为 $h$。

整个函数就可以写成 $F=\max(B,\max_{I\text{ 同色}}h_I)$。其中 $B$ 是与剩余颜色无关的保底；初始窗口 $[l,r]$ 的权值为 $r-l+1$。

权值和支持分别回答两个问题：“能保证多少”和“需要满足什么”。前面 $00\,x\,11$ 的例子，删去 Bob、翻转右侧以后，支持有 $4$ 个位置，权值却仍然是 $3$。这正是保留权值的意义。

为什么还能照常消元

Alice 删点，权值不变。Bob 合并权值为 $u,v$ 的两父，新权值取 $\min(u,v)$，因为两个分支都必须提供保证。

可以逐阈值检查这件事：$\max(u,v)\ge k$ 等价于至少一个值不小于 $k$，$\min(u,v)\ge k$ 等价于两个值都不小于 $k$。所以取出所有权值至少为 $k$ 的条件，看到的仍是上一节的布尔消元。

也就是说，权值为 $h$ 的条件，一次性代表了它对所有 $k\le h$ 的贡献。决策顺序仍由 $p$ 决定，并没有改变 minimax 的顺序。

支持缩成至多一个位置时，该权值并入 $B$；不超过 $B$ 的条件可以忽略。为了把低答案单独处理，后面主结构维护 $G=\max(2,F)$，初始 $B=2$，只考虑 $k\ge3$。若最后得到 $G=2$，第 9 节会用一个常数时间判定恢复答案 $1$ 或 $2$。

一次消元产生的是一串嵌套条件

固定阈值 $k>B$，所有左父中只取权值至少为 $k$、左端点最靠右的；所有右父中只取右端点最靠左的。它们拼出的支持最小，支配这个阈值下的其他配对。

随着 $k$ 增大，可选父条件越来越少，最优左端点只能左移，最优右端点只能右移。因此同一次 Bob 消元产生的条件，权值递增，支持依次向外扩张。

先记住这个性质。它既能帮助压缩条件，也会让正序在线维护变成双指针。

还有一个与 $typ=2$ 有关的观察：倒序消掉所有时刻大于 $q$ 的自由位置后，得到的就是前缀 $q$ 对应的博弈函数。此时给剩余自由位置代入实际决策，给固定位置代入 $p_i\le q$ 时的实际值、否则的原固定值，就能求出答案。

因此可以先用 $p,a$ 确定这些函数的结构，再正序代入 $A$。强制在线限制的是实际决策的使用时机，条件的生成关系仍然可以提前算好。

3. 大批原始合并，其实只是一族滑动窗口

最初有 $O(n^2)$ 个窗口，显然不能真的建出来。先区分两类条件：未经 Bob 合并的叫原始条件，经过合并的叫历史条件。

原始条件很好理解：删掉 Alice，相当于留下一个通配位置；删掉 Bob，所有跨过它的原始窗口都消失，所以这个位置成了分隔点。

考虑当前要删除的 Bob $x$。最近的已删 Bob 为 $L,R$，最近的剩余位置为 $l,r$，缺失时使用哨兵 $0,n+1$。令 $P_x=\max(l+1,L+1)$、$Q_x=\min(r-1,R-1)$。也就是：$[P_x,Q_x]$ 这段原坐标范围，只剩下 $x$ 一个位置，其余全是已删 Alice。

如果想选一个结束于 $x$ 的原始左父，就应尽量把原窗口向右挤。长度为 $k$ 时，它可以取 $[Q_x-k+1,Q_x]$，最大可取长度为 $U=Q_x-L$。右父对称，为 $[P_x,P_x+k-1]$，最大长度为 $V=R-P_x$。

由于整段 $[P_x,Q_x]$ 已经只剩一个点，其长度已被 $B$ 覆盖。故对 $k>B$，上述窗口都确实包含 $x$，并且还有另一个剩余点。

现在最自然的想法是：两侧原始父都能用时，就直接选它们，把所有这些阈值打包。不过需要先确认，历史父会不会把端点缩得更近。

带着同一个旧 Bob 的条件，只会形成包含链

给每个条件记一个用于分析的“生成范围”：原始条件取原窗口，合并时取两父范围的并，Alice 删点不改变它。这个范围仍是区间，其中的剩余位置就是支持；范围内每个已删 Bob 都出现在该条件的生成历史里。

关注某个已经删除的 Bob $z$。它刚被删除时，带着这段历史的新条件由小到大嵌套。这个关系以后仍会保持。

原因是，若其中一个条件参与删除 $x$ 的合并，它包含 $x$；其余还能存活的条件不含 $x$，就只能是它的子集。合并后的新支持把它们一起包含进去，而本次产生的新支持之间本来也嵌套。Alice 删点则只会同时缩小这些集合。

所以，生成范围包含同一个已删 Bob 的存活条件，支持始终构成一条包含链。 可以把它理解为：一段共同的消元历史只能沿着这条链继续扩张，不能分叉成两个交叉的支持。

这就解释了原始父为什么优先

设历史左父 $I$ 结束于 $x$，能与右父 $J$ 配对。它们各至少有两个点，支持只交于 $x$。

$I$ 的生成范围不能包含 $x$ 右边的已删 Bob $z$。否则，取 $J$ 的一个右侧剩余点 $y$，必有 $x<z<y$：若 $y\le z$，$y$ 就也落在 $I$ 的范围中。于是 $J$ 的范围同样包含 $z$，但两份支持各有对方没有的点，与刚才的包含链矛盾。

因此 $I$ 的出生 Bob 在 $x$ 左边，它的生成范围也包含最近的分隔点 $L$，从而包含 $(L,x]$ 内全部剩余位置。原始左父可以完全放在 $(L,R)$ 内，左端点自然不会更靠左。右侧同理。

令 $C_x=\min(U,V)$。所有 $B<k\le C_x$ 都可以优先取两个原始父，合并后只是同一对窗口随 $k$ 向外扩张。把出生时的保底记为 $B_x$，这一整族条件只需保存中心 $x$、参数 $P_x,Q_x$ 和允许权值段 $[B_x+1,C_x]$，称为一个原始家族。

于是每个 Bob 至多保存一个家族。真正需要逐条生成的，只剩 $k>\max(B,C_x)$ 的尾部。

4. 历史条件很长，但新增权值只占一小段

只把原始前缀打包还不够。历史条件可能越来越长，看起来尾部仍然可能很大。接着追问：一个长条件所支持的那些小答案，真的还需要再生成一次吗？

先看一个结束于当前 Bob $x$ 的历史左父 $I$，权值为 $h>B$，并且它能与右父配对。沿着它的生成历史，找最靠右的已删 Bob。上一节已经说明历史中没有 $x$ 右侧的 Bob，又因为生成范围覆盖出生 Bob 到 $x$，所以这个最靠右的 Bob 恰好是 $z=L$。

右边界来自一个原始窗口

追溯到删除 $z$ 的那一步，设相关祖先的权值为 $H\ge h$。它的右父一定是原始父：否则一个合法历史右父还会带来更靠右的出生 Bob，与 $z$ 最靠右矛盾。

这个原始右窗口可以取 $[P_z,P_z+H-1]$。所以无论 $I$ 后来经过了多少次合并，它现在的右边界，最初都来自这个窗口。

这给出两个很有用的限制。

首先，窗口不能伸到当前后继 $r$，因为 $r$ 还活着，伸到它就会把它一直留在支持中。也不能伸到右侧已删 Bob $R$：$R$ 若当时已删，原始窗口不能跨过它；若后来删除，就会进入这条生成历史。因此 $P_z+H-1<\min(r,R)=Q_x+1$，进而有 $h\le Q_x+1-P_z$。

其次，把同一个窗口缩到长度 $k<x-P_z+1$，它的右端点就还没碰到 $x$。配上当时对应的左父，已经能得到一份不依赖 $x$ 的、权值至少为 $k$ 的保证，其支持包含于高权条件。

还要确认这份保证在后续消元中不会丢失。沿着高权条件继续走：小条件若不含下一次删除的 Bob，就直接存活；若包含，它就是对应的右父，可以与高权合并中的同一个左父配对，得到一个仍不含 $x$ 的更小条件。后续出生 Bob 都在 $z$ 左侧，所以这个传递过程始终合法。Alice 删点也保持包含关系。

若生成器选择了更小的支持，就换用那个条件；若它在更早的步骤也被剪掉，就换用当时保留下的更小替代。按消元时间归纳即可。小条件若已经缩成单点，则 $B$ 已经达到 $k$，也就不在当前讨论的 $k>B$ 范围内。

因此对 $B<k\le h$，只要 $k<x-P_z+1$，当前就已经有一个不含 $x$、支持包含于 $I\setminus\{x\}$ 的存活条件。它会在本次 Bob 消元中保留下来，新合并对这个阈值是多余的。

这个观察的直觉是：窗口还没长到 $x$ 的那些答案，早就在左边得到了保证；只有刚刚开始依赖 $x$ 的部分，才值得重新生成。

真正需要枚举的权值，被夹在两条边界之间

记两侧候选能配对的最大公共容量为 $K_x$，没有候选时取 $0$。

若 $U\le V$，非原始尾部一定使用历史左父。小于 $x-P_L+1$ 的阈值已有旧条件覆盖，所以令 $T_x=\max(B,C_x,x-P_L)$，只枚举 $T_x<k\le K_x$。而刚才又得到 $K_x\le Q_x+1-P_L$，两式相减就是 $K_x-T_x\le Q_x-x+1$。

注意右边只剩 $x$ 右侧那段已删 Alice 空隙的长度，再加 $1$。历史父可能跨得很远，但它带来的新增权值被压进了这段局部空隙。

若 $V<U$，完全对称：令 $T_x=\max(B,C_x,Q_R-x)$，得到 $K_x-T_x\le x-P_x+1$。所需历史分隔点不存在时，对应尾部直接为空。

现在记 Alice、Bob 总数为 $n_A,n_B$。一个 Alice 位置至多被计入某个 Bob 的右侧空隙一次：这个 Bob 删除后会形成分隔点，挡住更左边的 Bob，而二者之间原本就没有别的未删 Bob。左侧同理。

于是 $\sum_x\max(0,K_x-T_x)\le n_B+2n_A=O(n)$。

这控制的是枚举的整个权值带。因此保存的显式条件、未保存的生成尝试、后面要开的权值桶，全部只有线性总量。至此，状态数量的问题解决了：原始窗口隐式维护，每个 Bob 一个原始家族，再加 $O(n)$ 条显式条件。

5. 条件确定以后，怎样强制在线

先假设倒序已经生成了所有家族和显式条件，以及每个前缀的保底 $B_q$。第 7 节再说明这些信息如何在线性时间内算出。

正序只做一件事：实际决策逐个到来时，求当前仍能成立的条件中的最大权值。三类条件恰好有三种简单的表示。

原始窗口看坏点间隙

对目标色 $c$，把不能作为颜色 $c$ 通配位置的点称为坏点：

加入坏点哨兵 $0,n+1$。相邻坏点之间全是已知色 $c$ 或 Alice 通配符，所以最长原始窗口就是最大相邻距离减一。一次实际赋值只会拆分或合并常数个间隙。

这里原固定点执行后也要换成实际颜色，不能继续使用原来的 $a_i$。

原始家族看中心两侧的距离

家族中心 $x$ 尚未执行时，只要求一侧同色、另一侧反色。记 $x$ 左右最近的颜色 $c$ 坏点分别为 $l_c,r_c$，则左侧取 $c$、右侧取 $c\oplus1$ 时，可满足的最大权值为 $v_c(x)=\min(Q_x-l_c,r_{c\oplus1}-P_x)$。

这个式子就是让两个原始窗口都停在坏点之前。将它截到出生时的允许权值段，低于下界则记为 $0$，两方向取最大即可。中心执行时，家族整体过期。

改变一个坏点，最多影响相邻的未来 Bob 中心：更远中心的查询会先被中间那个 Bob 挡住，因为未来 Bob 本身就是两色坏点。因此一次赋值也只需重算常数个家族。

原始条件没有内部消元 Bob，家族只有出生中心造成一次左右异色，所以这两类条件可以直接使用实际颜色计算。

显式条件要把两个方向分开

设一条显式条件出生于倒序删除 Bob 的时刻 $t$，其中剩余 Bob 的最大时间戳为 $d$；这类最大时间戳在集合为空时统一取 $0$。倒序第一次遇到内部 Bob 就会消去它，所以这条条件对应的正序存续范围是 $d\le q<t$。

再看固定颜色。把条件的两种方向编号为 $c=0,1$，记归一化原固定色为 $c$ 的位置中，最大时间戳为 $h_c$。方向 $c$ 要生效，原本异色的固定点必须已经全部执行完，可以被真实决策覆盖。因此最早生效时刻为 $\rho_c=\max(d,h_{c\oplus1})$；若 $\rho_c\ge t$，这个方向没有生效机会。

此后还要检查已执行点是否满足这个方向。好处是：一旦被某个实际决策破坏，这个方向就永远失效。 造成冲突的过去决策不会再次改变。

为什么要分方向？例如两个固定点原来都是 $0$，后来依次被实际决策改成 $1$，不分方向的“同色”就可能经历真、假、真。把“全 $0$”和“全 $1$”分别处理，每个方向的激活和失效才是单调的。

同批条件统一以出生 Bob 的颜色给方向编号，公共位置相位相同；又因为支持嵌套，权值越大，需要等候的 Bob、异色固定点只会越多，故激活时刻不减。实际冲突也从某个条件开始向所有更大支持传播。

因此每批每方向只需两个指针：激活前缀的末端 $u$ 只增，尚未判死前缀的末端 $v$ 只减，当前候选就是下标 $\min(u,v)$。

把各批次的候选权值放入整数桶。取最大候选时检查它；若失败，就降低对应的 $v$ 并重算桶；若成功，就找到了最大显式贡献。失败检查每次永久排除一个候选，成功检查每次输出至多一次，所以总检查次数为 $O(n)$。

这样，在线问题已经缩成了常数个邻居更新、线性次事件，以及线性次条件判真。

6. 条件判真：让失败沿着表达式传播

每次拿到一个条件，再去查询区间颜色，会给每次检查增加一个数据结构的代价。换个角度：条件之间本来就有父子关系，一次实际赋值破坏的东西能否沿着这些关系直接传播？

给位置 $i$ 定义两个字面量 $X_i^c(q)=[q<p_i]\lor[A_{p_i}=c]$。它表达的是“目前还没有一个实际决策证明位置 $i$ 不能取 $c$”。位置未执行时两者都真；执行后恰好一种永远变假。原固定色的限制已经由激活时刻处理，因此这里也从两个真值开始。

每个条件的一个方向都是若干字面量的合取。用带两个方向的 AND 节点保存它，引用附一个翻转位，用来交换两个方向。翻色变成交换两个槽位，没有非单调的 NOT 门。

若左右父在当前 Bob $x$ 的相位分别为 $\alpha,\beta$，新条件记录 $C_{\rm new}(c)=C_L(c\oplus\alpha)\land C_R(c\oplus\beta\oplus1)$ 即可。

被删掉的变量，居然可以留在表达式里

两父都含 $x$，但上式没有真正删掉它。这样成立的原因是：新条件只在 $q<t=p_x$ 时使用，这段时间 $X_x^0=X_x^1=1$。等到 $x$ 的实际值到来，条件已经过期了。

祖先中消去的 Bob 执行得更晚，也满足这个关系；原始窗口边界多包含的已删 Alice 同理。于是条件先过期，多余字面量才可能失效，保留它们不影响任何有效查询。

这一步利用了时间维度，省去了表达式中的删点。每次合并只需要常数个父引用，整个依赖关系是一张 DAG。

为 AND 节点建立反向边。一个方向变假，就通知使用它的父节点；父方向若首次变假，再继续传播。每个节点每方向至多失效一次，每条边只处理常数次，总费用就是图的大小。

这是常见的摊还思路：让每次传播都对应一个永久发生的变化。难点转移成了把图建得足够小。

原始区间合取也要共享

引用显式父时，可以直接复用旧节点。引用原始父或家族父时，需要常数次原始区间合取，询问总数 $Q=O(n)$，而且全部区间都能在读入 $A$ 前确定。

若把每次区间询问拆成线段树节点，会多出一个对数。这里利用合取的幂等性：一项重复合取没有影响，因此区间可以像 RMQ 的稀疏表那样，用两个重叠段表示。再把稀疏表放到合适的块粒度上，便能限制总规模。

取微块长 $b$ 为不超过 $\sqrt w$ 的最大二次幂，每 $b$ 个微块组成一个宏块，宏块长度为 $\Theta(w)$。

• 宏块内部对完整微块建合取稀疏表，节点数为 $O((n/b)\log b)=O(n)$。
• 完整宏块之间再建一层稀疏表，节点数为 $O((n/b^2)\log n)=O(n)$。

一个任意区间拆成两个微块残段、至多两个宏块内的整微块区间，以及一段完整宏块，只需要常数个引用。

微块残段怎么处理？长度为 $b$ 的块只有 $b(b+1)/2\le w$ 种非空区间，可以把区间类型放进一个机器字。对每个块内位置预处理一个掩码，标出所有包含它的类型；各微块只标记实际被查询的类型。

位置 $i$ 被赋值为 $c$ 时，将包含 $i$ 的类型掩码与方向 $c\oplus1$ 仍有效的类型字相与，就得到本次新失效的区间。枚举这些位并通知相应节点，每个被询问类型每方向只枚举一次。

未询问类型无需分配节点。类型的紧凑编号用位计数得到，挂接表通过计数排序建立。公用的块内掩码表预处理为 $O(b^3)=O((\log n)^{3/2})=O(n)$，小规模取常数底层即可。

因此区间表示、AND 图和全部传播都只有 $O(n+Q)=O(n)$ 的时间与空间。这一段的两个关键性质很清楚：幂等性让区间分解可以重叠，单调性让失效传播只需付一次费用。

7. 倒序预处理：从父条件继承信息

回到倒序部分。第 4 节已经把生成尝试数压到线性，现在要保证找父条件、维护下一次消元时刻、更新保底，也都只花线性总时间。

候选只在下一次内部 Bob 出现时取出

一条显式条件只需记住其中剩余 Bob 的最大时间戳 $d$，挂到时间桶 $d$。倒序处理到它时，这条条件第一次碰到内部 Bob：若该 Bob 是支持端点，它可以参与本次配对；否则直接消失。每条条件只进入一个这样的桶。

扫描本次候选，求出左右两侧最大可用容量，取小就得到 $K_x$。当前的短权值带为 $[T_x+1,K_x]$，历史候选按权值放桶，后缀取最优端点，就得到每个阈值的最优父。一定是先求 $T_x$ 再开桶，这样全部桶长才受第 4 节的线性界控制。

原始父由第 3 节的窗口公式直接得到。历史家族也只有相邻 $L,R$ 两个可能有用，因为家族不能跨过中心之外的其他已删 Bob。

具体地，用 $\operatorname{prevCut}(z),\operatorname{nextCut}(z)$ 表示中心外侧相邻的已删 Bob。设家族 $z$ 当前容量 $H_z$ 为出生上界与 $Q_z-\operatorname{prevCut}(z)$、$\operatorname{nextCut}(z)-P_z$ 三者的最小值。若 $z<x$，它作左父时取最小家族权值 $s=\max(k,x-P_z+1)$，要求 $s\le\min(H_z,r-P_z)$，左端点就是不小于 $Q_z-s+1$ 的第一个剩余位置。右父对称，取 $s=\max(k,Q_z-x+1)$，要求 $s\le\min(H_z,Q_z-l)$，右端点为不大于 $P_z+s-1$ 的最后一个剩余位置。

这些不等式分别要求：家族窗口碰到 $x$，但不能越过它的下一个剩余邻居。当前 $k>B\ge B_z$，出生时的允许下界也自动满足。因此每次家族查询只需常数次算术和前后继操作。

在短权值带上，逐个 $k$ 生成最小支持、赋权值 $k$ 即可；同批同支持也可以合并，保留较大权值。两种方式都只有线性次生成操作。

固定点只取最大值，Bob 才需要一个支持序列

在线阶段需要的摘要是 $d,h_0,h_1$。看它们如何随合并变化，就能避免每次重新查询整个动态区间。

原固定点在倒序中从不删除。两父按当前 Bob 的相位对齐，翻转右父后，分别对两种原固定颜色的最大时间戳取最大值即可。删掉的 Bob 不是固定点，摘要中没有需要扣除的内容。合法端点父从原端点到当前 Bob 之间只删过 Alice，相对相位不变，所以端点相位也只需由父条件继承两个比特。

剩余 Bob 的最大时间戳则要处理端点删除。不过新支持恰好是“左父删末端、右父删首端、两者拼接”，可以直接给每个条件保存一个支持序列。

把原 Bob 按坐标编号，一个连续编号段 $[u,v]$ 作为一个原子，摘要为其中的最大时间戳。原始父用一个原子表示，家族父用出生 Bob 两侧的两个原子表示。删除端点 Bob 只需缩短端原子，空了就弹出；随后拼接两份序列。

父条件可能在同批中被多个孩子选中，旧版本必须保留，因此使用全持久化可拼接双端队列。修正后的 Kaplan–Okasaki–Tarjan 结构支持两端插入、弹出、拼接，在顺序执行下每次确定性摊还 $O(1)$；其持久化与摊还界见 Ponsonnet、Pottier 的 Verified Persistent Catenable Deques。

这是本文调用的高级数据结构结果。它允许旧版本共享内部重整的等价表示，使相同历史结构的整理结果能够复用；在持久化场景中，不能只把普通双端队列的摊还分析照搬到每个分支。给节点附上最大值这一结合摘要，每次结构操作仍只多常数工作。

现在每次生成只做常数次队列操作，总操作数为 $O(n)$，总时间和分配空间也就是 $O(n)$。这里的思路是沿生成关系继承答案，只维护合并真正改变的边界。

原子上的查询都是静态 RMQ

原 Bob 编号段、两种原固定颜色的时间戳，都可以用静态 RMQ 查询。下面的保底处理还需要静态第二小值，总共只有常数套数组。

长度为 $m$ 的数组按 $b=\Theta(\log(m+2))$ 分块。为每个右端点保存本块单调栈的位掩码：查询块内 $[l,r]$ 时，截去 $l$ 之前的位，再取第一个有效位，就是最值位置。每项只入栈、出栈一次，预处理 $O(m)$。

块内单调栈已经删去了不会成为任何后缀最值的项，所以一个字就装下了所有有用候选。完整块的最值再建稀疏表，规模为 $O((m/b)\log(m/b+2))=O(m)$。查询拆成两个残块和中间完整块，仍为 $O(1)$。

找到最小值位置以后，再查它左右两段的最小值，就得到第二小值。

保底何时增加，也可以提前预约

显式条件缩成至多一个点时，权值并入 $B$。给原固定点静态时间戳 $0$，其余点时间戳 $p_i$，查询支持原坐标区间的第二小值 $s$。

为什么一个静态查询能看出动态的单点时刻？因为倒序删点就是按时间戳从大到小删除，原固定点永不删除。最后两个留下的位置决定了何时变成单点；出生前已删除的点时间戳都不小于出生时刻 $t$，不会干扰这两个最小值。

若 $s\ge t$，新条件已经恒真。否则，当且仅当 $s>d$ 时预约在倒序删去时刻 $s$ 后更新 $B$：这说明先把条件缩成单点的是 Alice；若先遇到内部 Bob，条件就会先参与另一轮消元。每条条件至多预约一个事件。

原始条件只需看局部空隙。Bob 分隔块内，只含剩余点 $y$ 的最长原始窗口，是该块与 $(\operatorname{preAlive}(y),\operatorname{nextAlive}(y))$ 的交。删掉 Alice 后，只有相邻两个剩余点的窗口可能变长；整块为空时，用整块长度更新 $B$。

家族也一样。设中心 $z$ 两侧最近剩余点为 $l,r$，再外侧为 $l_2,r_2$，当前容量为 $H_z$。只剩左点时，权值不超过 $\min(Q_z-l_2,r-P_z)$；只剩右点时，不超过 $\min(Q_z-l,r_2-P_z)$。两者取大，再与 $H_z$ 取小，落在允许权值段内就并入 $B$。

一次 Alice 删除只影响相邻两个已删 Bob 的家族，家族出生时也检查一次。这样保底检查和预约事件总共都是 $O(n)$ 次，便得到所有 $B_q$。

8. 剩下的对数，交给单调性和机器字

目前已经把所有工作化成线性次操作，还剩两类集合操作：找前后继，以及取全局最大权值。它们都有额外结构可用。

前后继：把一次性变化拆成只插和只删

对一个目标色，一个位置的坏点成员状态至多改变一次：Bob 执行后从一个坏点集删除，Alice 执行后向一个坏点集插入，固定点改色时对两色各作一次删除或插入。

因此坏点集可拆成“初始坏点的只删集合”和“新增坏点的只插集合”。两者前驱取大、后继取小，就是答案。倒序剩余点只删、已删 Bob 只插，也属于同一类问题。

对单调集合按每字 $w$ 位存放。字内前后继直接做位运算，跨字时只需要跳过一段连续空字。给每个空字记录所属空区间，并为区间保存左右端点，就能最坏 $O(1)$ 跳到最近非空字。

维护这些区间时，只删集合不断合并空区间，只插集合不断切开空区间。每次只重标号较小一侧：合并时，被重标号元素所在区间至少翻倍；分裂时至少减半。因此每个字只被重标号 $O(\log(n/w+2))$ 次。

这里把“小并大”的计费单位从单个位置换成了机器字。总共只有 $O(n/w)$ 个字，故 $Q$ 次操作的总时间为 $O(Q+(n/w)\log(n/w+2))=O(n+Q)$。

最大值：向下扫描可以由先前的上升付账

各贡献的权值都在 $[0,n]$ 中，按权值维护频次或批次链表，再用位集标记非空桶。我们始终只问全局最大值。

最大桶清空时，从当前字开始往下找；插入更大权值时，直接把最大值抬上去。设修改数为 $Q$，最大值的累计上升距离为 $V$。字编号累计上升至多 $O(Q+V/w)$，累计下降扫描不超过先前上升加初始高度，所以总费用为 $O(Q+n/w+V/w)$。

于是允许 $V$ 达到 $O(n\log n)$：每次机器操作能跨过 $\Theta(\log n)$ 个权值，仍然得到线性总时间。接下来需要控制的，正是整个过程中最大值的累计上升。

先给所有生成容量做一次小侧计费

第 4 节控制了短权值带的长度，但一个批次的权值仍然可能很大。这里还需要 $\sum_xK_x=O(n\log n)$，以及原始家族容量之和 $\sum_xC_x=O(n\log n)$。

如果没有 Alice 空隙，倒序插入 Bob 就是在不断分裂原坐标间隙，生成容量受较短一侧限制，很容易想到对较小子间隙计费。现在的麻烦只是：历史窗口会带着出生时的 Alice 空隙越过分隔点。把这些空隙也算成重量，就能恢复同一个分裂过程。

令 $g_x^L=x-P_x$、$g_x^R=Q_x-x$。每个 Alice 在左右两类空隙中各至多被计一次，所以 $\sum_x(g_x^L+g_x^R)\le2n_A$；哨兵的这两个量取 $0$。

给相邻分隔点 $L<R$ 的间隙定义重量 $\mu(L,R)=R-L+g_L^L+g_R^R+\sum_{L<y<R,\ a_y=-2}(g_y^L+g_y^R)$。内部 Bob 尚未插入，先把它们将来需要的空隙重量也放在间隙里。

插入 $x$ 后，$g_x^R$ 随左子间隙、$g_x^L$ 随右子间隙分配，恰好有 $\mu(L,R)=\mu(L,x)+\mu(x,R)$。初始总重量为 $W=n+1+\sum_y(g_y^L+g_y^R)=O(n)$。

第 4 节对历史父的容量限制，改写后是左父至多 $x-L+g_L^L+g_x^R+1$，右父至多 $R-x+g_x^L+g_R^R+1$。原始父也满足它；遇到哨兵时该侧只考虑原始父。因此 $K_x\le1+\min(\mu(L,x),\mu(x,R))$，而 $C_x$ 的界连这个 $1$ 都不需要。

每次把较小子间隙的重量计给其中的单位重量。一个单位被计费后，所在间隙至少缩小一半，最多被计费 $O(\log W)$ 次。于是两项容量和都是 $O(n\log n)$。

这个重量的定义就是为了让分裂守恒，并覆盖历史窗口携带的那一点额外长度。总重量仍是线性的，因而可以照常使用“小侧至多付对数次”的计费。

三类贡献的上升都受这个界控制

显式批次。 每个方向的候选下标为 $\min(u,v)$，其中 $u$ 只增、$v$ 只减。两指针交会前，候选只会变大；交会后，只会变小。因此权值单峰，累计上升不超过本批 $K_x$，两方向总上升为 $O(\sum_xK_x)$。

原始家族。 到只删坏点集合的距离只增，到只插坏点集合的距离只减。把两侧和两种集合拆开后，某个方向的贡献仍可写成“一个不减量与一个不增量的较小者”，所以也单峰。

家族出生时左右的分隔 Bob 执行得更晚，在中心执行前始终是两色坏点，因此方向贡献不超过出生容量 $C_x$。截取允许权值段也保持单峰性；两方向总累计上升为 $O(\sum_xC_x)$。

原始窗口间隙。 插入坏点只会分裂间隙，不增加最大值。删除坏点将长为 $a,b$ 的两段合并，最大间隙增加至多 $\min(a,b)$，因为合并前最大值已经至少为 $\max(a,b)$。

忽略后来插入的坏点，对应被合并的两段只会更长。在这个只合并的过程中，把较短段的长度计给其中的单位长度，每次被计费后所在段至少翻倍，因此总费用为 $O(n\log n)$，也就控制了真实过程的累计上升。

全局最大值的正向变化不超过各贡献正向变化之和。三类桶都有 $Q=O(n)$、$V=O(n\log n)$，代入逐字扫描的费用式，得到 $O(n)$。

字内最高位、最低位和位计数可视为常数时间操作。若模型没有直接提供，也可以将一个字拆成常数个 $\lfloor\tfrac12\log_2 n\rfloor$ 位小块，用 $O(\sqrt n)$ 大小的预处理表完成，不影响总界。

9. 低答案与完整流程

答案为 $1$，就是整个序列交替

记最终颜色为 $b_i$。最长同色段为 $1$，等价于所有 $b_i\oplus(i\bmod2)$ 相同，问题就变成了所有“奇偶颜色”能否一致。

在当前前缀后，把实际执行值与未来原固定值都视为已知，记剩余 Alice 数为 $c$。Bob 能保证答案为 $1$，当且仅当已知奇偶颜色不冲突，并且满足下面之一：

• $c=0$；
• $c=1$，没有已知值，且唯一的 Alice 是剩余游戏的第一个决策者。

有已知颜色可参照时，Alice 可以取相反的奇偶颜色；有两个 Alice 时，她们也可以取不同颜色。唯一 Alice 若不是第一个决策者，她行动时也能参照之前 Bob 的颜色。反过来，剩下全是 Bob 时可以统一取色；唯一 Alice 最先行动时，Bob 跟随她即可。

维护已知两色计数和剩余 Alice 数，每次决策只需 $O(1)$。主结构算出 $G=2$ 时用它恢复答案，否则直接使用 $G$。

将前面的部分接起来

倒序阶段只使用 $p,a$：建立静态 RMQ，维护剩余点和 Bob 分隔点；每个 Bob 生成至多一个原始家族，在短权值带内生成显式条件，继承支持摘要和表达式，登记保底、激活与过期事件。

正序先处理第 $0$ 个前缀。此后每次读入一个实际决策，更新字面量并传播失效，修改坏点间隙和相邻家族，处理激活、过期事件，再懒删失效的最大显式候选。取保底、原始窗口、原始家族、有效显式条件的最大贡献，最后恢复可能的低答案。

强制在线时，读入整数与上一答案异或后取最低位，得到本次真实决策。整个正序过程只使用已解码前缀；$typ=1$ 在得到 $\operatorname{ans}_0$ 后直接输出即可。

最后检查每类工作付了多少次费用：

全部结构只保存 $O(n)$ 个条件、节点、引用和桶。因此整道题在上述 word-RAM 模型下，按输入输出的机器字数计，为确定性摊还 $O(n)$ 时间、$O(n)$ 空间。