显示原始代码
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int sum;
int size;
Node *son[2];
Node() {
son[0] = nullptr;
son[1] = nullptr;
size = 0;
sum = 0;
}
Node(int x) {
son[0] = nullptr;
son[1] = nullptr;
size = 1;
sum = x;
}
void inc(bool is_root) {
Node *t0 = son[0], *t1 = son[1];
int t0_size = size - (son[1] == nullptr ? 0 : son[1]->size);
if (t0 == nullptr && t0_size > 0) {
t0 = new Node();
t0->size = t0_size;
t0->sum = t0->size & 1;
} else if (t0 != nullptr) {
t0->sum ^= (t0->size & 1);
}
if (t1 == nullptr) {
} else {
t1->inc(false);
}
son[0] = t1;
son[1] = t0;
sum = 0;
sum ^= (son[0] == nullptr ? 0 : son[0]->sum);
sum ^= (son[1] == nullptr ? 0 : son[1]->sum);
if (!is_root)
sum <<= 1;
}
};
class MultiSet {
private:
Node *root;
public:
MultiSet() { root = new Node(); }
int getSum() { return root->sum; }
void inc() { root->inc(true); }
void insert(int t) {
Node *cur = root;
root->size++;
for (int flag = t & 1; t; t >>= 1, cur = cur->son[flag], flag = t & 1) {
if (cur->son[flag] != nullptr) {
cur->son[flag]->sum ^= t;
cur->son[flag]->size++;
} else {
cur->son[flag] = new Node(t);
}
}
root->sum = (root->son[0] == nullptr ? 0 : root->son[0]->sum) ^
(root->son[1] == nullptr ? 0 : root->son[1]->sum);
}
};
int main() {
int n;
MultiSet ms;
cin >> n;
for (int i = 0; i < n; ++i) {
int op;
scanf("%d", &op);
if (op == 1) {
ms.inc();
} else if (op == 2) {
int num;
scanf("%d", &num);
ms.insert(num);
}
printf("%d\n", ms.getSum());
}
return 0;
}