查询添加一个数字，删除一个数字，用 A[i] xor X 替换数组中的所有 A[i]，找到 K 个最小数字的总和

Question

问题是：

Initially, the sequence is empty. There are n queries and 4 types of queries:

Add(x): add x to the sequence, if there is already x in the sequence, still add x.

Remove(x): remove x from the sequence 1 times.

Xor(x): replace all N of the sequence with N xor x.

Sum(K): find sum of the k smallest elements in the sequence.

0 <= x, n, K <= 10^5

For each query sum(x), output the sum of the x smallest elements in the sequence.

Input:
7
Add(4)      // A[] = {4}
Remove(3)   // A[] = {4}
Add(2)      // A[] = {4, 2}
Sum(2)      // A[] = {4, 2} => Output: 6
Xor(2)      // A[] = {4^2, 2^2} = {6, 0}
Sum(1)      // A[] = {6, 0} => Output: 0
Sum(2)      // A[] = {6, 0} => Output: 6

我通过以下方式解决了问题：

Use a vector A to hold the sequence of numbers, and an array Count[] where Count[x] is the number of occurrences of x in A. Initially A is empty, and every Count[x] = 0.

For each Add(x) query, I add x to A, and Count[x] = Count[x]+1

For each Remove(x) query, if Count[x] = 0 then skip, otherwise, remove x from A and Count[x] = Count[x]-1

For each Xor(x) query, replace every A[i] with A[i]^x

For each Sum(x) query, sort A in ascending value, take the sum of the first x numbers

看来我的方法复杂度为O(n^2)，所以对于n <= 100000，上面的算法是行不通的。有没有更好的方法来解决这个问题？非常感谢。

我的代码可以运行在 n <= 5000 的情况下运行良好。就是这样：

int Count[100001];
vector<int> A;
void Add(int x) {
     A.push_back(x);
     Count[x] = Count[x]+1;
}
void Remove(int x) {
     if (Count[x] == 0) return;
     Count[x] = Count[x]-1;
     auto Find = find(A.begin(), A.end(), x);
     A.erase(Find);
}
void Xor(int x) {
     for (int& i : A)
         i = i^x;
}
int Sum(int x) {
     int Num = 0, S = 0;
     for (int i : A) {
        if (Num + 1 > x) return S;
        S = S + i; Num = Num + 1;
     }
     return S;
}

Answer 1

我将描述一个支持Add(x)/Remove(x)/Count()/SumXorWith(x)的数据结构（returns所有元素的总和xor x；不修改序列）然后概述如何扩展它是一个完整的解决方案，其中每个操作都是 O(log^2 n)（将 n 视为操作数和值的上限）。

首先观察Count和SumXorWith可以用来计算，对于每个位的位置，有多少个数字设置了该位置（例如，对于低位，它是(Count() + SumXorWith(0) - SumXorWith(1)) / 2).相反，维持这些计数就足够了。在伪代码中：

*** Variables, initially zero:

count : int
bit_count : int[17]

*** Operations:

Add(x):
increment count
for j from 0 to 16, add the j'th bit of x to bit_count[j]

Remove(x):
decrement count
for j from 0 to 16, subtract the j'th bit of x from bit_count[j]

Count():
return count

SumXorWith(x):
return the sum for j from 0 to 16 of
2**j * (if j'th bit of x = 0 then bit_count[j] else count - bit_count[j])

要扩展此数据结构以处理 Xor(x)/Sum()，我们可以为 x 中设置的每个位取 count - bit_count，但为了提高效率（我们稍后需要），有一个技巧。这个想法是我们存储序列 xor cum_xor。更多伪代码：

*** Additional variable, initially zero

cum_xor : int

*** Operations:

Add(x): super.Add(x xor cum_xor)
Remove(x): super.Remove(x xor cum_xor)
Xor(x): cum_xor <- cum_xor xor x
Count(): return super.Count()
Sum(): return super.SumXorWith(cum_xor)

最后，我们需要通过选择处理 Sum(x)。坦率地说，这是乏味的部分。我们在 big-endian 位模式上设置了一个高度为 17（log2(100000) 的上限）特里树，在特里树的每个节点上都使用上述数据结构之一。对于 Add/Remove，我们下降 trie，在每个节点处执行 Add/Remove。 Xor 我们像以前一样处理，通过更新 cum_xor。 Sum(x) 当然是最棘手的。从 trie 的根开始，我们检查当前节点。如果它最多有 x 个元素，就把它加起来。否则，它的“喜欢”child是同意cum_xor的，它的“不喜欢”child是不同意的。如果受欢迎的child至少有x个元素，那么我们可以对其进行递归操作，忽略不受欢迎的child。否则，我们对整个受欢迎的 child 求和并对不受欢迎的 child 进行递归运算，将 x 减少受欢迎的 child.

中的元素数量

（为了最大的实际效率，我们想要比 trie 更高 fan-out 的东西，并且可能是叶子附近的天真实现，但这是我能做到的尽可能简单并且可能足够快。 )

查询添加一个数字，删除一个数字，用 A[i] xor X 替换数组中的所有 A[i]，找到 K 个最小数字的总和

Queries add a number, remove a number, replace all A[i] in array with A[i] xor X, find sum of K smallest numbers

algorithm

xor