AT_arc203_d.[ARC203D] Insert XOR

有一个由 $0$ 和 $1$ 组成的长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。现在有 $Q$ 个查询。第 $q$ 个查询如下：

• 给定一个 $1$ 到 $N$ 之间的整数 $i_q$。将 $A_{i_q}$ 的值从 $0$ 变为 $1$，或从 $1$ 变为 $0$。

每处理完一个查询后，请回答以下问题：

考虑所有满足下述条件的 $0$ 和 $1$ 组成的数列 $B=(B_1,B_2,\dots,B_{|B|})$：

• 可以对 $B$ 进行任意次如下操作，使其变为序列 $A$：
  • 选择一个 $1$ 到 $|B|-1$ 之间的整数 $i$。
  • 在 $B_i$ 和 $B_{i+1}$ 之间插入 $B_i\oplus B_{i+1}$。

总是存在满足条件的 $B$。请输出所有可能的 $|B|$ 的最小值。

输入按以下格式从标准输入读入：

$N$ $A_1$ $A_2$ $\dots$ $A_N$ $Q$ $i_1$ $i_2$ $\vdots$ $i_Q$

请输出共 $Q$ 行答案。第 $q$ 行输出处理完第 $q$ 个查询后的问题答案。

数据范围

• $3 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 1$
• $1 \leq Q \leq 5 \times 10^5$
• $1 \leq i_q \leq N$
• 输入的所有数均为整数

样例解释 1

当 $A=(1,0,0)$ 时，$|B|$ 取 $B=(1,0,0)$ 时最小。
当 $A=(1,1,0)$ 时，$|B|$ 取 $B=(1,0)$ 时最小。

由 ChatGPT 4.1 翻译