3224: Tyvj 1728 普通平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 14301 Solved: 6208
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
题目链接：BZOJ 3224
刚学了一下treap，照着模版和自己的理解，果然数据结构很多都是码农题……可以发现treap就是一颗在插入和删除操作的时候会进行一些平衡调整的BST，就当是treap练手题了。
这题用离线下的离散化+线段树应该也是可以AC的，姿势有很多种就对了……
代码：
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 100010;
struct Node
{
int ls, rs, v, w, sz;
int rnd;
};
Node T[N];
int tot, root; void init()
{
tot = 0;
}
void pushup(int k)
{
T[k].sz = T[T[k].ls].sz + T[T[k].rs].sz + T[k].w;
}
void lturn(int &k)
{
int rs = T[k].rs;
T[k].rs = T[rs].ls;
T[rs].ls = k;
T[rs].sz = T[k].sz;
pushup(k);
k = rs;
}
void rturn(int &k)
{
int ls = T[k].ls;
T[k].ls = T[ls].rs;
T[ls].rs = k;
T[ls].sz = T[k].sz;
pushup(k);
k = ls;
}
void ins(int &k, int v)
{
if (!k)
{
k = ++tot;
T[k].ls = T[k].rs = 0;
T[k].v = v;
T[k].w = T[k].sz = 1;
T[k].rnd = rand();
}
else
{
++T[k].sz;
if (v == T[k].v)
++T[k].w;
else if (v < T[k].v)
{
ins(T[k].ls, v);
if (T[T[k].ls].rnd < T[k].rnd)
rturn(k);
}
else
{
ins(T[k].rs, v);
if (T[T[k].rs].rnd < T[k].rnd)
lturn(k);
}
}
}
void del(int &k, int v)
{
if (!k)
return ;
if (T[k].v == v)
{
if (T[k].w > 1)
{
--T[k].w;
--T[k].sz;
return ;
}
if (T[k].ls * T[k].rs == 0)
k = T[k].ls + T[k].rs;
else
{
if (T[T[k].ls].rnd < T[T[k].rs].rnd)
rturn(k);
else
lturn(k);
del(k, v);
}
}
else
{
--T[k].sz;
if (v < T[k].v)
del(T[k].ls, v);
else
del(T[k].rs, v);
}
}
int query_rank(int k, int x)
{
if (!k)
return 0;
else
{
if (T[k].v == x)
return T[T[k].ls].sz + 1;
else if (x < T[k].v)
return query_rank(T[k].ls, x);
else
return T[T[k].ls].sz + T[k].w + query_rank(T[k].rs, x);
}
}
int query_kth(int k, int pos)
{
if (!k)
return 0;
if (pos <= T[T[k].ls].sz)
return query_kth(T[k].ls, pos);
else if (pos > T[T[k].ls].sz + T[k].w)
return query_kth(T[k].rs, pos - T[T[k].ls].sz - T[k].w);
else
return T[k].v;
}
void query_pre(int k, int v, int &ans)
{
if (!k)
return;
if (T[k].v < v)
{
ans = k;
query_pre(T[k].rs, v, ans);
}
else
query_pre(T[k].ls, v, ans);
}
void query_post(int k, int v, int &ans)
{
if (!k)
return ;
if (T[k].v > v)
{
ans = k;
query_post(T[k].ls, v, ans);
}
else
return query_post(T[k].rs, v, ans);
}
int main(void)
{
srand(987654321);
int n, x, ops, idx;
while (~scanf("%d", &n))
{
init();
while (n--)
{
scanf("%d%d", &ops, &x);
switch (ops)
{
case 1:
ins(root, x);
break;
case 2:
del(root, x);
break;
case 3:
printf("%d\n", query_rank(root, x));
break;
case 4:
printf("%d\n", query_kth(root, x));
break;
case 5:
query_pre(root, x, idx);
printf("%d\n", T[idx].v);
break;
case 6:
query_post(root, x, idx);
printf("%d\n", T[idx].v);
break;
}
}
}
return 0;
}