附文本代码
```cpp
#include <iostream>
#include <cstdlib>
using namespace std;
const int Maxn = 1e5 * 6;
struct Nodes
{
int fix , key , size;
int lson , rson;
int cnt;
}node[Maxn + 10];
int cnt = 0 , ans , root = 0;
bool print;
void update(int root)
{
int l = node[root].lson;
int r = node[root].rson;
node[root].size = node[l].size + node[r].size + node[root].cnt;
}
void lturn(int &root)
{
int tmp = node[root].lson;
node[root].lson = node[tmp].rson;
node[tmp].rson = root;
node[tmp].size = node[root].size;
update(root);
root = tmp;
}
void rturn(int &root)
{
int tmp = node[root].rson;
node[root].rson = node[tmp].lson;
node[tmp].lson = root;
node[tmp].size = node[root].size;
update(root);
root = tmp;
}
void insert(int a , int &root)
{
if(root == 0)
{
root = ++cnt;
node[cnt].key = a;
node[cnt].fix = rand();
node[cnt].size = node[cnt].cnt = 1;
return;
}
node[root].size++;
if(a == node[root].key)
{
node[root].cnt++;
}
else if(a > node[root].key)
{
int r = node[root].rson;
insert(a , node[root].rson);
if(node[r].fix < node[root].fix)
rturn(root);
}
else if(a < node[root].key)
{
int l = node[root].lson;
insert(a , node[root].lson);
if(node[l].fix < node[root].fix)
lturn(root);
}
}
int get_rank(int a , int root)
{
if(root == 0)
return 0;
if(node[root].key == a)
{
print = 1;
return node[node[root].lson].size + 1;
}
else if(node[root].key > a)
{
return get_rank(a , node[root].lson);
}
else if(node[root].key < a)
{
int tag = node[node[root].lson].size + node[root].cnt;
return tag + get_rank(a , node[root].rson);
}
return 0;
}
int get_key(int a , int root)
{
if(root == 0)
return 0;
int l = node[root].lson;
int r = node[root].rson;
if(a <= node[l].size)
return get_key(a , l);
a -= node[l].size;
if(a <= node[root].cnt)
{
print = 1;
return node[root].key;
}
a -= node[root].cnt;
return get_key(a , r);
}
void dfs(int root)
{
if(root == 0)
return;
dfs(node[root].lson);
cout << node[root].key << ' ';
dfs(node[root].rson);
}
int main()
{
srand(20031125);
ios::sync_with_stdio(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
char type;
int x;
cin >> type >> x;
if(type == 'I')
{
insert(x , root);
}
if(type == 'R')
{
print = 0;
ans = get_rank(x , root);
if(print == 1)
cout << ans << endl;
else
cout << -1 << endl;
}
if(type == 'K')
{
print = 0;
ans = get_key(x , root);
if(print == 1)
cout << ans << endl;
else
cout << -1 << endl;
}
if(type == 'Y')
dfs(root);
}
return 0;
}
```
by SkyLiYu @ 2018-07-08 10:04:23