```cpp
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const double alpha = 0.75;
struct node
{
node *lson, *rson;
int num, tree_size, real_size;
bool ban;
inline bool isbad()
{
return this->real_size * alpha <
max(this->lson->real_size, this->rson->real_size);
}
inline void update()
{
this->real_size = (int)!this->ban + this->lson->real_size + this->rson->real_size;
this->tree_size = 1 + this->lson->tree_size + this->rson->tree_size;
}
};
//根节点
node root, *rt = &root;
//内存池子
vector<node *> nodes;
//新建节点（再写结构体内显得太长），返回节点地址
node *newnode(int val = 0, int rs = 1, int ts = 1, node *l = NULL, node *r = NULL)
{
node *rt = new (node);
rt->lson = l, rt->rson = r;
rt->ban = false;
rt->tree_size = rt->real_size = 1;
return rt;
}
//中序遍历（拍扁过程）
void dfs(node *rt, vector<node *> &nodes)
{
if (rt == NULL)
return;
dfs(rt->lson, nodes);
if (!rt->ban)
nodes.push_back(rt);
dfs(rt->rson, nodes);
if (rt->ban)
delete rt;
}
//重新建树，返回根节点
node *build_tree(vector<node *> &nodes, int l, int r)
{
if (l > r)
return NULL;
int mid = (l + r) >> 1;
node *rt = nodes[mid];
rt->lson = build_tree(nodes, l, mid - 1);
rt->rson = build_tree(nodes, mid + 1, r);
return rt;
}
//重新建树（拍扁+重构）
void rebuild(node *&rt)
{
nodes.clear();
nodes.push_back(NULL);
dfs(rt, nodes);
rt = build_tree(nodes, 1, nodes.size() - 1);
}
void Insert(node *&rt, int val)
{
if (rt = NULL)
{
rt = newnode(val);
return;
}
else
{
rt->real_size++, rt->tree_size++;
if (rt->num >= val)
Insert(rt->lson, val);
else
Insert(rt->rson, val);
if (rt->isbad())
rebuild(rt);
}
}
//获得一个值是val的点的最小rank
int getrank(int val)
{
node *now = rt;
int ans = 1;
while (rt != NULL)
{
if (now->num >= val)
now = now->lson;
else
{
ans += now->lson->real_size + (int)!now->ban;
now = now->rson;
}
}
return ans;
}
//获得一个rank是rk的节点value
int getvalue(int rk)
{
node *now = rt;
while (now != NULL)
{
if (!now->ban && now->lson->real_size + 1 == rk)
return now->num;
if (now->lson->real_size >= rk)
now = now->lson;
else
{
rk -= now->lson->real_size + (int)!now->ban;
now = now->rson;
}
}
return -1;
}
//删除rank是rk的节点
void delete1(node *rt, int rk)
{
if (!rt->ban && rt->lson->real_size + 1 == rk)
{
rt->ban = true;
rt->real_size--;
return;
}
rt->real_size--;
if (rt->lson->real_size + (int)!rt->ban >= rk)
delete1(rt->lson, rk);
else
delete1(rt->rson, rk - rt->lson->real_size - (int)!rt->ban);
}
//删除权值是val的节点
void delete2(node *rt, int val)
{
if (getvalue(getrank(val)) != val)
return;
//如果这个点不存在，就删不了
delete1(rt, getrank(val));
}
int prefix(int val)
{
if (getvalue(getrank(val)) != val)
return -1;
else
return getvalue(getrank(val) - 1);
}
int latefix(int val)
{
if (getvalue(getrank(val)) != val)
return -1;
else
return getvalue(getrank(val) + 1);
}
int main()
{
int n;
scanf("%d", &n);
while (n--)
{
int opt, x;
scanf("%d%d", &opt, &x);
switch (opt)
{
case 1:
Insert(rt, x);
break;
case 2:
delete2(rt, x);
break;
case 3:
printf("%d\n", getrank(x));
break;
case 4:
printf("%d\n", getvalue(x));
break;
case 5:
printf("%d\n", prefix(x));
break;
case 6:
printf("%d\n", latefix(x));
break;
default:
break;
}
}
return 0;
}
```
GG
by Jelly_Goat @ 2019-06-02 08:37:37
膜拜指针大佬（别人的代码不好调，别人的指针更不好调）
by 音乐王子 @ 2019-06-02 08:54:33
@[Jelly_Goat](/space/show?uid=122927)
其实这种长的代码最好还是自己调，基本上没人愿意帮你看这种代码的。。。。
by RiverFun @ 2019-06-02 09:27:49
@[Steve_braveman](/space/show?uid=96570)
调了一早上了
还是没出来
（sign~）
by Jelly_Goat @ 2019-06-02 10:47:53
@[Jelly_Goat](/space/show?uid=122927) 另外提醒一句，尽量不要写指针，因为有时候会出一些玄学bug你根本看不出来~~别问我怎么知道的~~
by RiverFun @ 2019-06-02 10:49:47
@[Steve_braveman](/space/show?uid=96570)
（面对C++）
我：我错了QAQ 我以后再也不写指针了 （sign~）
（c++回过头去）
C++：来，继续RE
by Jelly_Goat @ 2019-06-02 11:04:53