分数: 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 满足条件。 找到最小可能值 |B|.
- 通过在 B,可以使其匹配序列 A:
- 选择一个整数 i 之间 1 和 |B|-1,包括在内。
- 插入 B_i\oplus B_{i+1} 之间 B_i 和 B_{i+1}.
约束
- 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