﻿ACDream 1063 平衡树-Ocrosoft

# ACDream 1063 平衡树

### 平衡树

Time Limit: 4000/2000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

#### Input

1. insert X ，加入数 X
2. qmax X ，求第2种操作的答案
3. qmin X ，求第3种操作的答案

```1
4
insert 1
insert 2
qmin 1
qmax 1```

```0
3```

#### Hint

Huge input and output. Please do not use: 1. cin ans cout of C++ 2. scanner of Java(Maybe BufferedReader is quicker)

#### Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
#define ms(a) memset(a,0,sizeof(a))
typedef long long ll;
const int INF = INT_MAX;
const int MAXN = 50000 + 10;
using namespace std;
struct Trie
{
int ch[MAXN][3];
int num;
void insert(int x)
{
int u = 0;
for (int i = 30; i >= 0; i--)
{
int s = ((1 << i)&x);//获取x的二进制表示的第i位
if (s)
{
if (!ch[u][1])
{
num++;
ch[u][1] = num;
}
u = ch[u][1];
}
else
{
if (!ch[u][0])
{
num++;
ch[u][0] = num;
}
u = ch[u][0];
}
}
return;
}
int qmin(int x)
{
int u = 0;
int ret = 0;
for (int i = 30; i >= 0; i--)
{
int s = ((1 << i)&x);
if (s)
{
if (ch[u][1])
{
u = ch[u][1];
ret += (1 << i);//转回10进制
}
else u = ch[u][0];
}
else
{
if (ch[u][0])u = ch[u][0];
else
{
u = ch[u][1];
ret += (1 << i);
}
}
}
return ret;
}
int qmax(int x)
{
int u = 0;
int ret = 0;
for (int i = 30; i >= 0; i--)
{
int s = ((1 << i)&x);
if (s)
{
if (ch[u][0])
u = ch[u][0];
else
{
u = ch[u][1];
ret += (1 << i);
}
}
else
{
if (ch[u][1])
{
u = ch[u][1];
ret += (1 << i);
}
else u = ch[u][0];
}
}
return ret;
}
}trie;
int main()
{
int T;
cin >> T;
while (T--)
{
ms(trie.ch);
trie.num = 0;
int n;
cin >> n;
char s[10];
for (int i = 1; i <= n; i++)
{
int x;
scanf("%s%d", s, &x);
if (!strcmp(s, "insert"))trie.insert(x);
else if (!strcmp(s, "qmax"))printf("%d\n", trie.qmax(x)^x);
else if (!strcmp(s, "qmin"))printf("%d\n", trie.qmin(x)^x);
}
}
return 0;
}```