对给定数组进行 XOR 查询

Question

给定一个包含 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)
中解决它

Answer 1

假设你的数字不超过一些标准常数，比如 2³² 或 2⁶⁴，我们可以在常数时间内完成，通过分别计算位。

您将需要：

记住数组中有多少个数
记住二进制定位系统中每个位置有多少个点亮的位。

这是你的示例，扩展为位，最不重要的位在顶部：

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”位的计数。

Answer 2

感谢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;
}

对给定数组进行 XOR 查询

XOR queries on a given array

algorithm

xor

segment-tree

bitwise-xor