显示原始代码
#include <iostream>
#include <cstdio>
class TreeNode {
public:
int num;
TreeNode *left = NULL;
TreeNode *right = NULL;
bool isDelete = false;
TreeNode(int num) { this->num = num; }
};
class Tree {
public:
TreeNode *root = NULL;
void insert(int num);
void plusOne() {
plusOne(root);
showAnswer(true);
}
private:
int lastAnswer = 0;
void showAnswer(bool needRecalculate, int newNumber = 0);
void plusOne(TreeNode *node);
int yuHuo(TreeNode *node, int number);
};
void Tree::insert(int num) {
TreeNode *newNode = new TreeNode(num);
if (root == NULL) {
root = newNode;
showAnswer(false, num);
return;
}
TreeNode *temp = root;
while (1) {
if (num == temp->num) {
temp->isDelete = true;
showAnswer(false, num);
return;
} else if (num < temp->num) {
if (temp->left == NULL) {
temp->left = newNode;
showAnswer(false, num);
return;
}
temp = temp->left;
} else {
if (temp->right == NULL) {
temp->right = newNode;
showAnswer(false, num);
return;
}
temp = temp->right;
}
}
}
void Tree::plusOne(TreeNode *node) {
if (node == NULL) {
return;
}
node->num++;
plusOne(node->left);
plusOne(node->right);
}
void Tree::showAnswer(bool needRecalculate, int newNumber) {
if (needRecalculate == false) {
lastAnswer ^= newNumber;
} else {
lastAnswer = yuHuo(root, newNumber);
}
std::cout << lastAnswer << std::endl;
}
int Tree::yuHuo(TreeNode *node, int number) {
if (node == NULL) {
return number;
}
number ^= node->num;
number = yuHuo(node->left, number);
return yuHuo(node->right, number);
}
inline int read() {
int num = 0, sign = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') {
sign = -1;
}
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
num = num * 10 + ch - '0';
ch = getchar();
}
return num * sign;
}
int main(int argc, const char *argv[]) {
std::cin.sync_with_stdio(false);
std::cin.tie(0);
int n = read();
Tree tree = Tree();
int funcNum, num;
for (int i = 0; i < n; i++) {
funcNum = read();
if (funcNum == 1) {
tree.plusOne();
} else {
num = read();
tree.insert(num);
}
}
return 0;
}