对给定数组进行 XOR 查询
XOR queries on a given array
给定一个包含 n 个整数的数组,索引从 1->n。任务是执行 Q 个给定的查询,并在每个查询 .
后打印数组的 总和
我们可以执行三种类型的操作:
- 1 X:将 X 添加到数组中(其索引将为 n+1、n+2、...)
- 2 Y:从数组中删除索引为 Y 的元素
- 3 Z:对数组中的每个元素i,执行i^Z (i xor Z)
示例:
输入
arr[] = {2, 3, 9, 5, 6, 6}, Q = 5
1 3
3 5
2 2
3 2
2 7
输出: 34 37 31 27 23
解释:
1 3 -> arr[] = {2, 3, 9, 5, 6, 6, 3} -> 总和 = 34
3 5 -> arr[] = {7, 6, 12, 0, 3, 3, 6} -> 总和 = 37
2 2 -> arr[] = {7, 12, 0, 3, 3, 6} -> 总和 = 31
3 2 -> arr[] = {5, 14, 2, 1, 1, 4} -> 总和 = 27
2 7 -> arr[] = {5, 14, 2, 1, 1} -> 总和 = 23
P/S: 我正在尝试用线段树解决问题,但我无法用 XOR 运算符更新树。还有其他方法可以解决这个问题吗?我试图在 O(n.logn)
中解决它
假设你的数字不超过一些标准常数,比如 232 或 264,我们可以在常数时间内完成,通过分别计算位。
您将需要:
- 记住数组中有多少个数
- 记住二进制定位系统中每个位置有多少个点亮的位。
这是你的示例,扩展为位,最不重要的位在顶部:
2 3 9 5 6 6 3 | sum
-------------------------
0 1 1 1 0 0 1 | 4
1 1 0 0 1 1 1 | 5
0 0 0 1 1 1 0 | 3
0 0 1 0 0 0 0 | 1
现在,这意味着有
4
“第一”位点亮
5
“第二”位点亮
3
“第三”位点亮并且
1
“第四”位点亮。
- 号码的个数是
7
。
- 这些数字的总和是
34
我们现在用 5
对它进行异或运算,在二进制中是 0101
,所以现在会有
7 - 4 = 3
“第一”位点亮
5
“第二”位点亮
7 - 3 = 4
“第三”位点亮
1
“第四”位点亮
如果我们总结一下,我们得到 3 * 2^0 + 5 * 2^1 + 4 * 2^2 + 1 * 2^3 = 37
(现在 ^
我的意思是求幂而不是异或)。
这就是每次弹出异或运算时你要做的。添加和删除数字是比较容易的部分,因为您遍历了它们的位并相应地调整了数组中点亮的“i
-th”位的计数。
感谢Maurycyt我已经解决了这个问题。下面是我的代码,以防有人需要它
const int MAX = 1e5 + 5;
const int MAXBIT = 32;
int n, q, num, xor_add;
int arr[MAX], sum[32];
int getSum()
{
int res = 0;
for(int i = 0; i < MAXBIT; i++)
res += sum[i]*(1<<i);
return res;
}
void updateXor(int x){
xor_add ^= x;
for(int i = 0; i < MAXBIT; i++)
if(x & (1<<i))sum[i] = num - sum[i];
}
void add(int x){
++num;
arr[n++] = x;
for(int i = 0; i < MAXBIT; i++)
if(x & (1<<i))sum[i]++;
}
void remv(int i){
--num;
int x = arr[i-1]^xor_add;
for(int i = 0; i < MAXBIT; i++)
if(x & (1<<i))sum[i]--;
}
int main()
{
cin >> n >> q;
num = n;
for(int i = 0; i < n; i++)cin >> arr[i];
for(int i = 0; i < MAXBIT; i++)
for(int j = 0; j < n; j++)
if(arr[j] & (1<<i))sum[i]++;
while(q--){
int id, x;
cin >> id >> x;
if(id == 1)add(x);
else if(id == 2)remv(x);
else updateXor(x);
cout << getSum() << '\n';
}
return 0;
}
给定一个包含 n 个整数的数组,索引从 1->n。任务是执行 Q 个给定的查询,并在每个查询 .
后打印数组的 总和我们可以执行三种类型的操作:
- 1 X:将 X 添加到数组中(其索引将为 n+1、n+2、...)
- 2 Y:从数组中删除索引为 Y 的元素
- 3 Z:对数组中的每个元素i,执行i^Z (i xor Z)
示例:
输入
arr[] = {2, 3, 9, 5, 6, 6}, Q = 5
1 3
3 5
2 2
3 2
2 7
输出: 34 37 31 27 23
解释:
1 3 -> arr[] = {2, 3, 9, 5, 6, 6, 3} -> 总和 = 34
3 5 -> arr[] = {7, 6, 12, 0, 3, 3, 6} -> 总和 = 37
2 2 -> arr[] = {7, 12, 0, 3, 3, 6} -> 总和 = 31
3 2 -> arr[] = {5, 14, 2, 1, 1, 4} -> 总和 = 27
2 7 -> arr[] = {5, 14, 2, 1, 1} -> 总和 = 23
P/S: 我正在尝试用线段树解决问题,但我无法用 XOR 运算符更新树。还有其他方法可以解决这个问题吗?我试图在 O(n.logn)
中解决它假设你的数字不超过一些标准常数,比如 232 或 264,我们可以在常数时间内完成,通过分别计算位。
您将需要:
- 记住数组中有多少个数
- 记住二进制定位系统中每个位置有多少个点亮的位。
这是你的示例,扩展为位,最不重要的位在顶部:
2 3 9 5 6 6 3 | sum
-------------------------
0 1 1 1 0 0 1 | 4
1 1 0 0 1 1 1 | 5
0 0 0 1 1 1 0 | 3
0 0 1 0 0 0 0 | 1
现在,这意味着有
4
“第一”位点亮5
“第二”位点亮3
“第三”位点亮并且1
“第四”位点亮。- 号码的个数是
7
。 - 这些数字的总和是
34
我们现在用 5
对它进行异或运算,在二进制中是 0101
,所以现在会有
7 - 4 = 3
“第一”位点亮5
“第二”位点亮7 - 3 = 4
“第三”位点亮1
“第四”位点亮
如果我们总结一下,我们得到 3 * 2^0 + 5 * 2^1 + 4 * 2^2 + 1 * 2^3 = 37
(现在 ^
我的意思是求幂而不是异或)。
这就是每次弹出异或运算时你要做的。添加和删除数字是比较容易的部分,因为您遍历了它们的位并相应地调整了数组中点亮的“i
-th”位的计数。
感谢Maurycyt我已经解决了这个问题。下面是我的代码,以防有人需要它
const int MAX = 1e5 + 5;
const int MAXBIT = 32;
int n, q, num, xor_add;
int arr[MAX], sum[32];
int getSum()
{
int res = 0;
for(int i = 0; i < MAXBIT; i++)
res += sum[i]*(1<<i);
return res;
}
void updateXor(int x){
xor_add ^= x;
for(int i = 0; i < MAXBIT; i++)
if(x & (1<<i))sum[i] = num - sum[i];
}
void add(int x){
++num;
arr[n++] = x;
for(int i = 0; i < MAXBIT; i++)
if(x & (1<<i))sum[i]++;
}
void remv(int i){
--num;
int x = arr[i-1]^xor_add;
for(int i = 0; i < MAXBIT; i++)
if(x & (1<<i))sum[i]--;
}
int main()
{
cin >> n >> q;
num = n;
for(int i = 0; i < n; i++)cin >> arr[i];
for(int i = 0; i < MAXBIT; i++)
for(int j = 0; j < n; j++)
if(arr[j] & (1<<i))sum[i]++;
while(q--){
int id, x;
cin >> id >> x;
if(id == 1)add(x);
else if(id == 2)remv(x);
else updateXor(x);
cout << getSum() << '\n';
}
return 0;
}