← 返回题目列表

AtCoder · arc203_d

D. 插入异或

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

有一个整数序列 A=(A_1,A_2,\dots,A_N) 长度 N 组成 0 和 1。 你被给予 Q 查询。 的 q第查询如下:

  • 一个整数 给出了 i_q 之间 1 和 N 。改变 A_{i_q} to 1 如果是 0,并 0 如果是 1.

处理每个查询后,找到以下问题的答案:

考虑序列 B=(B_1,B_2,\dots,B_{|B|}) 组成 0 和 1 满足以下条件:

  • 通过在 B,可以使其匹配序列 A:
    • 选择一个整数 i 之间 1 和 |B|-1,包括在内。
    • 插入 B_i\oplus B_{i+1} 之间 B_i 和 B_{i+1}.
可以证明,总是存在 B 满足条件。 找到最小可能值 |B|.

约束

  • 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
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

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

输出

总共输出答案 Q 行。 的 q- 第行应包含处理后问题的答案 q第一个查询。


示例输入 1

3
0 0 0
2
1
2

示例输出 1

3
2

当 A=(1,0,0), |B| 最小化为 B=(1,0,0)。 什么时候 A=(1,1,0), |B| 最小化为 B=(1,0).


示例输入 2

8
0 1 0 0 1 1 1 0
3
1
4
1

示例输出 2

5
2
3