← 返回题目列表

AtCoder · icpc2013summer_day3_j

I. A 加 B

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

有一天,Ikta 无法想出一个在编程竞赛训练营中提出问题的想法,因此他咨询了一位朋友。

Ikta-kun:“我想问一个不使用这种算法就无法解决的问题。你有什么想法吗?”

朋友:“那为什么不考虑这样的事情呢?”

就这样,朋友想出了一个想法,成为下面问题的基础。 给定

2進数A,B,处理以下查询。

  • 输出查询:max{x 用二进制表示时1的个数 | 输出 A \leq x < A+B }

  • 更改查询: 从 A的最低有效位开始i反转位(0-原点)

  • B变更查询: B的最低有效位开始i反转位(0-原点)

i请注意,第 th 位以 0 为起点表示。 换句话说,A从最低有效位开始的第 0 位表示最低有效位。

输入

输入按以下格式给出。

N A B
Q1
...
QN

第一行给出了查询数N和二进制数A和B。

以下查询在第 2 行到第 N+1 行中给出。

  • Q

  • A i

  • B i

Q 输出查询,A i,B i分别是A的最低有效位开始i位,B的最低有效位开始i表示反转位的更改查询。

约束

输入中的每个变量都满足以下约束。

  • 1 \leq N < 300,000

  • 1 \leq |A|,|B| \leq 300,000 (|A|是A长度) 在查询

  • A i 中 0 \leq i < |A|

  • B i 中 0 \leq i < |B|

  • B永远不会是 0

输出

将每个输出查询的答案打印在一行上。

样本输入 1

4 10000 00101
Q
A 0
B 1
Q

样本输入 1 的输出

3
4

在第一个输出查询中 A=10000, B=00101, A+B=10101因此,找到x是 10011

在以下输出查询中 A=10001, B=00111, A+B=11000因此,找到x是 10111

示例输入 2

9 0110111101 0010100111
Q
B 4
Q
A 4
Q
B 9
Q
A 8
Q

样本输入 2 的输出

9
9
9
10
9