## 【bzoj1728】普通平衡树 原

LOI_xczhw

QAQ

QAQ人生第一个维护数的splay
QAQQQQQQQ

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
struct tr
{
tr *ch[2],*f;
int v,sz,cnt;
bool dir()
{
return f -> ch[1] == this;
}
void maintain()
{
sz = cnt + ch[0] -> sz + ch[1] -> sz;
return;
}
void setc(tr *p,int d)
{
(ch[d] = p) -> f = this;
return;
}
}tree[MAXN],*root,*null;
int tot = 0;
tr* newnode(int x,tr* fa = null)
{
tr *p = tree + (tot ++);
p -> f = fa;
p -> ch[0] = p -> ch[1] = null;
p -> sz = p -> cnt = 1;
p -> v = x;
return p;
}
void reset()
{
tot = 0;
null = newnode(0);
null -> sz = null -> cnt = 0;
root = null;
return;
}
void rot(tr *x)
{
tr *p = x -> f;
int d = x -> dir();
p -> f -> setc(x,p -> dir());
p -> setc(x -> ch[d ^ 1],d);
p -> maintain();
x -> setc(p,d ^ 1);
x -> maintain();
if(p == root)
root = x;
return;
}
void splay(tr* x,tr* to = null)
{
while(x -> f != to)
{
if(x -> f -> f == to)
rot(x);
else
x -> dir() == x -> f -> dir() ? (rot(x -> f),rot(x)) : (rot(x),rot(x));
}
}
void insert(int x)
{
if(root == null)
{
root = newnode(x);
return;
}
tr* p = root;
while(p != null)
{
p -> sz ++;
if(p -> v == x)
{
p -> cnt++;
break;
}
int d = x > p -> v;
if(p -> ch[d] == null)
{
p -> ch[d] = newnode(x,p);
p = p -> ch[d];
break;
}
p = p -> ch[d];
}
splay(p);
return;
}
tr* find(int x)
{
tr* p = root;
while(p != null)
{
if(p -> v == x)
break;
int d = x > p -> v;
p = p -> ch[d];
}
splay(p);
return p;
}
void del(int x)
{
tr *p = find(x);
splay(p);
p -> sz --;
if(--p -> cnt)
return;
if(p -> ch[0] == null){root = p -> ch[1];root -> f = null;return;}
if(p -> ch[1] == null){root = p -> ch[0];root -> f = null;return;}
p = p -> ch[0];
while(p -> ch[1] != null)
p = p -> ch[1];
splay(p,root);
p -> setc(root -> ch[1],1);
p -> f = null;
p -> maintain();
root = p;
return;
}
int find_hj(int x)
{
tr* p = root;
int ans = 0;
while(p != null)
{
if(x < p -> v)
ans = p -> v,p = p -> ch[0];
else
p = p -> ch[1];
}
return ans;
}
int find_qq(int x)
{
tr* p = root;
int ans = 0;
while(p != null)
{
if(x > p -> v)
ans = p -> v,p = p -> ch[1];
else
p = p -> ch[0];
}
return ans;
}
int num_to_pm(int x)
{
splay(find(x));
return root -> ch[0] -> sz + 1;
}
int pm_to_num(int x)
{
tr* p = root;
while(p != null)
{
int l = p -> ch[0] -> sz + 1;
int r = p -> ch[0] -> sz + p -> cnt;
if(l <= x && x <= r)
return p -> v;
int d = x > p -> ch[0] -> sz + p -> cnt;
if(d)
x -= p -> ch[0] -> sz + p -> cnt;
p = p -> ch[d];
}
return p -> v;
}

int n,q,x;
int main()
{
reset();
scanf("%d",&n);
while(n --)
{
scanf("%d",&q);
switch(q)
{
case 1:scanf("%d",&x);insert(x);break;
case 2:scanf("%d",&x);del(x);break;
case 3:scanf("%d",&x);printf("%d\n",num_to_pm(x));break;
case 4:scanf("%d",&x);printf("%d\n",pm_to_num(x));break;
case 5:scanf("%d",&x);printf("%d\n",find_qq(x));break;
case 6:scanf("%d",&x);printf("%d\n",find_hj(x));break;
}
}
return 0;
}``````

### LOI_xczhw

1.AVL树介绍 　　前面我们已经介绍了二叉搜索树。普通的二叉搜索树在插入、删除数据时可能使得全树的数据分布不平衡，退化，导致二叉搜索树最关键的查询效率急剧降低。这也引出了平衡二叉搜索...

02/13
0
0
《算法导论》学习笔记之Chapter13红黑树

u010483897
2017/12/13
0
0
java集合框架（四）：TreeMap

chenzanjin
2017/11/07
0
1
TYVJ1728普通平衡树题解（Treap学习笔记）

TYVJ1728普通平衡树题解（Treap学习笔记） 题意： 您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个)...

AndyGamma
2018/09/06
0
0
12.1 省选训练总结2(1) 点分治/平衡树

OwenOwl
2017/12/01
0
0

23分钟前
1
0

http://www.bubuko.com/infodetail-2592845.html

32分钟前
1
0
Consul+Spring boot的服务注册和服务注销

38分钟前
4
0
MySQL高可用之基于Galera复制跨地域节点分布的滥用

mysql使用教程 MySQL高可用之基于Galera复制跨地域节点分布的滥用 2018-11-22 02:15 8335 85 让我们再一次讨论MySQL高可用性（HA）和同步复制。 它是地理上分布区域上一些高可用性参考架构解...

rootliu
49分钟前
1
0
js判断pc还是移动端

var pcyidong =/(iPhone|iPad|iPod|iOS|Android)/i.test(navigator.userAgent); 如果pcyidong的值为false则用户的浏览器为pc端 如果pcyidong的值为true则用户浏览器为移动端 if (pcyidong =...

1
0