[R49F]集合 - 代码源竞赛平台

时空限制

3S/512M

题目描述

给定一个初始为空的整数集合 $S$。你需要处理 $Q$ 次操作，操作分为以下两种类型：

1. 1 x：如果集合 $S$ 中已经存在整数 $x$，则将 $x$ 从集合中删除；如果 $S$ 中不存在 $x$，则将 $x$ 插入集合中。
2. 2 x：给定一个整数 $x$，计算并输出以下表达式的值：$$\sum_{s \in S} \text{popcount} (s \oplus (s + x))$$

其中，$\oplus$ 表示按位异或运算，$\text{popcount}(v)$ 表示整数 $v$ 在二进制表示下 $1$ 的个数。

格式

输入格式

第一行包含一个整数 $Q$，表示操作次数。

接下来 $Q$ 行，每行包含两个整数 $op$ 和 $x$，分别表示操作类型和操作数。

输出格式

对于每个类型 $2$ 的查询，输出一行一个整数，表示计算结果。

样例

样例输入 #1

6
1 3
1 6
2 1
2 5
1 3
2 1

样例输出 #1

4
6
1

样例解释 #1

1. 1 3：集合变为 $S = \{3\}$。
2. 1 6：集合变为 $S = \{3, 6\}$。
3. 2 1：查询 $x=1$。
   • $s=3: 3 \oplus (3+1) = 3 \oplus 4 = 7$，$\text{popcount}(7) = 3$。
   • $s=6: 6 \oplus (6+1) = 6 \oplus 7 = 1$，$\text{popcount}(1) = 1$。
   • 结果为 $3 + 1 = 4$。
4. 2 5：查询 $x=5$。
   • $s=3: 3 \oplus (3+5) = 3 \oplus 8 = 11$，$\text{popcount}(11) = 3$。
   • $s=6: 6 \oplus (6+5) = 6 \oplus 11 = 13$，$\text{popcount}(13) = 3$。
   • 结果为 $3 + 3 = 6$。
5. 1 3：集合中已有 $3$，将其删除，集合变为 $S = \{6\}$。
6. 2 1：查询 $x=1$。
   • $s=6: 6 \oplus (6+1) = 1$，$\text{popcount}(1) = 1$。
   • 结果为 $1$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$Q \le$
$1$	$20$	$2000$
$2$	$80$	$2 \times 10^5$

对于 $100\%$ 的数据，$1 \le Q \le 2 \times 10^5$，$0 \le x < 2^{29}$。