3224: Tyvj 1728 普通平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 17048  Solved: 7429
[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

Sample Output

106465
84185
492737

HINT

1.n的数据范围:n<=100000
2.每个数的数据范围:[-2e9,2e9]

code

2018-07-01

 #include<cstdio>
#include<cctype> const int N = ; int siz[N],ch[N][],fa[N],cnt[N],data[N];
int Root,tn; #define ls ch[p][0]
#define rs ch[p][1] int son(int x) {
return x==ch[fa[x]][];
}
void pushup(int p) {
siz[p] = siz[ls] + siz[rs] + cnt[p];
}
void rotate(int x) {
int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
if (z) ch[z][c] = x;else Root = x;fa[x] = z;
ch[x][!b] = y;fa[y] = x;
ch[y][b] = a;if (a) fa[a] = y;
pushup(y),pushup(x);
}
void splay(int x,int rt) {
while (fa[x] != rt) {
int y = fa[x],z = fa[y];
if (z==rt) rotate(x);
else {
if (son(x)==son(y)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
}
int getrnk(int x) {
int p = Root,ans = ;
while (true) {
if (!p) return ans + ;
if (x == data[p]) {ans += siz[ls];splay(p,);return ans+;}
if (x < data[p]) p = ls;
else {
ans += siz[ls] + cnt[p];
p = rs;
}
}
}
int getkth(int k) {
int p = Root;
while (true) {
if (siz[ls] < k && k <= siz[ls] + cnt[p]) return data[p];
if (k <= siz[ls]) p = ls;
else {
k -= siz[ls] + cnt[p];
p = rs;
}
}
}
int Newnode(int pa,int d) {
++tn;siz[tn] = cnt[tn] = ;ch[tn][] = ch[tn][] = ;
data[tn] = d;fa[tn] = pa;
return tn;
}
void Insert(int x) {
if (!Root) {Root = Newnode(,x);return ;}
int p = Root,pa = ;
while (true) {
if (data[p]==x) {
cnt[p] ++;pushup(p);pushup(pa);splay(p,);return ; // Splay ?????????????????
}
pa = p; // ??!
p = ch[p][x > data[p]];
if (!p) {
p = Newnode(pa,x);
ch[pa][x > data[pa]] = p;
pushup(p),pushup(pa);splay(p,);
break;
}
}
}
void Clear(int p) {
siz[p] = cnt[p] = ch[p][] = ch[p][] = fa[p] = data[p] = ;
}
void Delete(int x) {
getrnk(x);
int &p = Root,tmp;
if (cnt[p]) {cnt[p]--;pushup(p);return ;}
if (!ls && !rs) {Clear(p);Root = ;return ;}
if (!ls || !rs) {tmp = p;p = ls?ls:rs;fa[p] = ;Clear(tmp);return ;}
int pre = ls;
while (ch[pre][]) pre = ch[pre][];
tmp = p;p = pre;
splay(p,);
ch[p][] = ch[tmp][];fa[ch[tmp][]] = p;
Clear(tmp);pushup(p);
}
int main() {
int T,opt,x;
scanf("%d",&T);
while (T--) {
scanf("%d%d",&opt,&x);
if (opt==) Insert(x);
else if (opt==) Delete(x);
else if (opt==) printf("%d\n",getrnk(x));
else if (opt==) printf("%d\n",getkth(x));
else if (opt==) printf("%d\n",getkth(getrnk(x)-));
else printf("%d\n",getkth(getrnk(x+)));
}
}

持续更新2018-05-02

 #include<cstdio>
#include<cctype> const int N = ; int siz[N],ch[N][],fa[N],cnt[N],data[N];
int Root,tn; #define ls ch[p][0]
#define rs ch[p][1] int son(int x) {
return x==ch[fa[x]][];
}
void pushup(int p) {
siz[p] = siz[ls] + siz[rs] + cnt[p];
}
void rotate(int x) {
int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
if (z) ch[z][c] = x;else Root = x;fa[x] = z;
ch[x][!b] = y;fa[y] = x;
ch[y][b] = a;if (a) fa[a] = y;
pushup(y),pushup(x);
}
void splay(int x,int rt) {
while (fa[x] != rt) {
int y = fa[x],z = fa[y];
if (z==rt) rotate(x);
else {
if (son(x)==son(y)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
}
int getrnk(int k) {
int p = Root,ans = ;
while (true) {
if (!p) return ans + ; // 没有这个点
if (k < data[p]) p = ls;
else {
ans += (ls?siz[ls]:);
if (k == data[p]) {
splay(p,);return ans + ;
}
ans += cnt[p];
p = rs;
}
}
}
int getkth(int k) {
int p = Root;
while (true) {
if (k <= siz[ls]) p = ls;
else {
k -= ls?siz[ls]:;
if (k<=cnt[p]) return data[p];
k -= cnt[p];
p = rs;
}
}
}
int Newnode(int pa,int d) {
++tn;siz[tn] = cnt[tn] = ;ch[tn][] = ch[tn][] = ;
data[tn] = d;fa[tn] = pa;
return tn;
}
void Insert(int x) {
if (!Root) {Root = Newnode(,x);return ;}
int p = Root,pa = ;
while (true) {
if (data[p]==x) {
cnt[p] ++;pushup(p);pushup(pa);splay(p,);return ; // Splay 为了更新新新加入节点后产生的变化。
}
pa = p; // 顺序!
p = ch[p][x > data[p]];
if (!p) {
p = Newnode(pa,x);
ch[pa][x > data[pa]] = p;
pushup(p),pushup(pa);splay(p,);
break;
}
}
}
void Clear(int p) {
siz[p] = cnt[p] = ch[p][] = ch[p][] = fa[p] = data[p] = ;
}
void Delete(int x) {
getrnk(x);
int &p = Root,tmp;
if (cnt[p]) {cnt[p]--;pushup(p);return ;}
if (!ls && !rs) {Clear(p);Root = ;return ;}
if (!ls || !rs) {tmp = p;p = ls?ls:rs;fa[p] = ;Clear(tmp);return ;}
int pre = ls;
while (pre) pre = ch[pre][];
tmp = p;p = pre;
splay(p,);
ch[p][] = ch[tmp][];fa[ch[tmp][]] = p;
Clear(tmp);pushup(p);
}
int main() {
int T,opt,x;
scanf("%d",&T);
while (T--) {
scanf("%d%d",&opt,&x);
if (opt==) Insert(x);
else if (opt==) Delete(x);
else if (opt==) printf("%d\n",getrnk(x));
else if (opt==) printf("%d\n",getkth(x));
else if (opt==) printf("%d\n",getkth(getrnk(x)-));
else printf("%d\n",getkth(getrnk(x+)));
}
}

再一次更新2018-05-01

 #include<cstdio>
#include<cctype> const int N = ;
int fa[N],ch[N][],siz[N],cnt[N],data[N];
int tn,Root; inline int read() {
int x = ,f = ;char ch = getchar();
for (; !isdigit(ch); ch=getchar()) if(ch=='-') f=-;
for (; isdigit(ch); ch=getchar()) x = x*+ch-'';
return x * f;
}
#define ls ch[p][0]
#define rs ch[p][1]
inline int son(int x) {
return x == ch[fa[x]][]; // -
}
inline void pushup(int x) {
siz[x] = siz[ch[x][]] + siz[ch[x][]] + cnt[x];
}
void rotate(int x) {
int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
if (z) ch[z][c] = x;else Root = x;fa[x] = z; // 调整x的位置
ch[x][!b] = y;fa[y] = x; // 调整y的位置
ch[y][b] = a;if (a) fa[a] = y; // 给y另一个子节点
pushup(y);pushup(x);
}
void splay(int x,int rt) {
while (fa[x] != rt) {
int y = fa[x],z = fa[y];
if (z==rt) rotate(x);
else {
if (son(x)==son(y)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
}
int getrnk(int k) { // 得到k的排名,位置
int p = Root,ans = ;
while (true) {
if (p == ) return ans + ;
if (k < data[p]) p = ls;
else {
ans += (ls ? siz[ls] : );
if (k==data[p]) {
splay(p,);return ans+;
}
ans += cnt[p];
p = rs;
}
}
}
int getkth(int k) { // 得到第k个数
int p = Root;
while (true) {
if (ls && k <= siz[ls]) p = ls;
else {
int tmp = (ls ? siz[ls] : ) + cnt[p];
if (k <= tmp) return data[p];
k -= tmp; p = rs;
}
}
}
void newnode(int x,int pa,int d) {
ch[x][] = ch[x][] = ;siz[x] = cnt[x] = ;
data[x] = d;fa[x] = pa;
}
inline void Insert(int x) { // 插入
if (Root==) {
++tn; Root = tn;newnode(tn,,x);return;
}
int p = Root,pa = ;
while (true) {
if (x==data[p]) {
cnt[p]++;pushup(p);pushup(pa);splay(p,);break;
}
pa = p;
p = ch[p][x > data[p]];
if (p==) {
p = ++tn;newnode(p,pa,x);
ch[pa][x > data[pa]] = p;
pushup(pa),splay(p,);break;
}
}
}
inline void Clear(int x) {
ch[x][] = ch[x][] = fa[x] = siz[x] = cnt[x] = data[x] = ;
}
inline void Delete(int x) { // 删除
getrnk(x);
int &p = Root;
if (cnt[p] > ) {cnt[p]--;pushup(p);return;}
if (!ls && !rs) {Clear(p);p = ;return;}
if (!ls || !rs) {
int tmp = p;p = ls==?rs:ls;fa[p] = ;Clear(tmp);return;
}
int tmp = p,pre = ls; // 找根节点的前一个-左子树的最右边
while (ch[pre][]) pre = ch[pre][];
splay(pre,);
rs = ch[tmp][];fa[ch[tmp][]] = p;
Clear(tmp);
pushup(p);
}
int main() {
int n = read();
while (n--){
int opt = read(),x = read();
if (opt==) Insert(x);
else if (opt==) Delete(x);
else if (opt==) printf("%d\n",getrnk(x));
else if (opt==) printf("%d\n",getkth(x));
else if (opt==) printf("%d\n",getkth(getrnk(x)-));
else printf("%d\n",getkth(getrnk(x+)));
}
return ;
}

更新了下板子

 #include<cstdio>

 const int N = ;
int fa[N],ch[N][],siz[N],cnt[N],data[N];
int tn,Root; inline char nc() {
static char buf[],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2) ? EOF :*p1++;
}
inline int read() {
int x = ,f = ;char ch=nc();
for (; ch<''||ch>''; ch = nc())
if (ch == '-') f = -;
for (; ch>=''&&ch<=''; ch = nc())
x = x*+ch-'';
return x * f;
}
inline int son(int x) {
return x == ch[fa[x]][]; // -
}
inline void pushup(int x) {
siz[x] = siz[ch[x][]] + siz[ch[x][]] + cnt[x];
}
inline void rotate(int x) {
int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
if (z) ch[z][c] = x;else Root = x;fa[x] = z; // 调整x的位置
ch[x][!b] = y;fa[y] = x; // 调整y的位置
ch[y][b] = a;if (a) fa[a] = y; // 给y另一个子节点
pushup(y);pushup(x);
}
inline void splay(int x,int rt) {
while (fa[x] != rt) {
int y = fa[x],z = fa[y];
if (z==rt) rotate(x);
else {
if (son(x)==son(y)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
}
inline int getpre(int x) { //得到第一个比x小的数
int p = Root,ans;
while (p) {
if (x <= data[p]) p = ch[p][];
else ans = p,p = ch[p][];
}
return ans;
}
inline int getsuc(int x) { // 得到第一个比x大的数
int p = Root,ans;
while (p) {
if (x >= data[p]) p = ch[p][];
else ans = p,p = ch[p][];
}
return ans;
}
inline int getk(int k) { // 得到k的排名
int p = Root,ans = ;
while (true) {
if (k < data[p]) p = ch[p][];
else {
ans += (ch[p][] ? siz[ch[p][]] : );
if (k==data[p]) {
splay(p,);return ans+;
}
ans += cnt[p];
p = ch[p][];
}
}
}
inline int getkth(int k) { // 得到第k个数
int p = Root;
while (true) {
if (ch[p][] && k <= siz[ch[p][]]) p = ch[p][];
else {
int tmp = (ch[p][] ? siz[ch[p][]] : ) + cnt[p];
if (k <= tmp) return data[p];
k -= tmp; p = ch[p][];
}
}
}
inline void Insert(int x) { // 插入
if (Root==) {
++tn; Root = tn;
ch[tn][] = ch[tn][] = fa[tn] = ;
siz[tn] = cnt[tn] = ;data[tn] = x;
return;
}
int p = Root,pa = ;
while (true) {
if (x==data[p]) {
cnt[p]++;pushup(p);pushup(pa);splay(p,);break;
}
pa = p;
p = ch[p][x > data[p]];
if (p==) {
tn++;
ch[tn][] = ch[tn][] = ;siz[tn] = cnt[tn] = ;
fa[tn] = pa;ch[pa][x > data[pa]] = tn;data[tn] = x; //-
pushup(pa),splay(tn,);break;
}
}
}
inline void Clear(int x) {
ch[x][] = ch[x][] = fa[x] = siz[x] = cnt[x] = data[x] = ;
}
inline void Delete(int x) { // 删除
getk(x);
if (cnt[Root] > ) {cnt[Root]--;pushup(Root);return;}
if (!ch[Root][] && !ch[Root][]) {Clear(Root);Root = ;return;}
if (!ch[Root][]) {
int tmp = Root;Root = ch[Root][];fa[Root] = ;Clear(tmp);return;
}
else if (!ch[Root][]) {
int tmp = Root;Root = ch[Root][];fa[Root] = ;Clear(tmp);return;
}
int tmp = Root,pre = ch[Root][];//可以是getpre(data[Root]);等价于下面的while
while (ch[pre][]) pre = ch[pre][];
splay(pre,);
ch[Root][] = ch[tmp][];
fa[ch[tmp][]] = Root;
Clear(tmp);
pushup(Root);
}
int main() {
int n = read();
while (n--){
int opt = read(),x = read();
if (opt==) Insert(x);
else if (opt==) Delete(x);
else if (opt==) printf("%d\n",getk(x));
else if (opt==) printf("%d\n",getkth(x));
else if (opt==) printf("%d\n",data[getpre(x)]);
else printf("%d\n",data[getsuc(x)]);
}
return ;
}

另一种写法,放一下吧

 #include<cstdio>

 const int N = ;
int fa[N],ch[N][],siz[N],cnt[N],data[N];
int tn,Root; inline char nc() {
static char buf[],*p1 = buf,*p2 = buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2) ? EOF :*p1++;
}
inline int read() {
int x = ,f = ;char ch=nc();
for (; ch<''||ch>''; ch = nc())
if (ch == '-') f = -;
for (; ch>=''&&ch<=''; ch = nc())
x = x*+ch-'';
return x * f;
}
inline int son(int x) {
return x == ch[fa[x]][]; // -
}
inline void pushup(int x) {
siz[x] = siz[ch[x][]] + siz[ch[x][]] + cnt[x];
}
inline void rotate(int x) {
int y = fa[x],z = fa[y],b = son(x),c = son(y),a = ch[x][!b];
if (z) ch[z][c] = x;else Root = x;fa[x] = z; // 调整x的位置
ch[x][!b] = y;fa[y] = x; // 调整y的位置
ch[y][b] = a;if (a) fa[a] = y; // 给y另一个子节点
pushup(y);pushup(x);
}
inline void splay(int x,int rt) {
while (fa[x] != rt) {
int y = fa[x],z = fa[y];
if (z==rt) rotate(x);
else {
if (son(x)==son(y)) rotate(y),rotate(x);
else rotate(x),rotate(x);
}
}
}
inline int getpre(int x) { //得到第一个比x小的数
int p = ch[Root][];
while (ch[p][]) p = ch[p][];
return p;
}
inline int getsuc(int x) { // 得到第一个比x大的数
int p = ch[Root][];
while (ch[p][]) p = ch[p][];
return p;
}
inline int getk(int k) { // 得到k的排名
int p = Root,ans = ;
while (true) {
if (k < data[p]) p = ch[p][];
else {
ans += (ch[p][] ? siz[ch[p][]] : );
if (k==data[p]) {
splay(p,);return ans+;
}
ans += cnt[p];
p = ch[p][];
}
}
}
inline int getkth(int k) { // 得到第k个数
int p = Root;
while (true) {
if (ch[p][] && k <= siz[ch[p][]]) p = ch[p][];
else {
int tmp = (ch[p][] ? siz[ch[p][]] : ) + cnt[p];
if (k <= tmp) return data[p];
k -= tmp; p = ch[p][];
}
}
}
inline void Insert(int x) { // 插入
if (Root==) {
++tn; Root = tn;
ch[tn][] = ch[tn][] = fa[tn] = ;
siz[tn] = cnt[tn] = ;data[tn] = x;
return;
}
int p = Root,pa = ;
while (true) {
if (x==data[p]) {
cnt[p]++;pushup(p);pushup(pa);splay(p,);break;
}
pa = p;
p = ch[p][x > data[p]];
if (p==) {
tn++;
ch[tn][] = ch[tn][] = ;siz[tn] = cnt[tn] = ;
fa[tn] = pa;ch[pa][x > data[pa]] = tn;data[tn] = x; //-
pushup(pa),splay(tn,);break;
}
}
}
inline void Clear(int x) {
ch[x][] = ch[x][] = fa[x] = siz[x] = cnt[x] = data[x] = ;
}
inline void Delete(int x) { // 删除
getk(x);
if (cnt[Root] > ) {cnt[Root]--;pushup(Root);return;}
if (!ch[Root][] && !ch[Root][]) {Clear(Root);Root = ;return;}
if (!ch[Root][]) {
int tmp = Root;Root = ch[Root][];fa[Root] = ;Clear(tmp);return;
}
else if (!ch[Root][]) {
int tmp = Root;Root = ch[Root][];fa[Root] = ;Clear(tmp);return;
}
int tmp = Root,pre = ch[Root][];//可以是getpre(data[Root]);等价于下面的while
while (ch[pre][]) pre = ch[pre][];
splay(pre,);
ch[Root][] = ch[tmp][];
fa[ch[tmp][]] = Root;
Clear(tmp);
pushup(Root);
}
int main() {
int n = read();
while (n--){
int opt = read(),x = read();
if (opt==) Insert(x);
else if (opt==) Delete(x);
else if (opt==) printf("%d\n",getk(x));
else if (opt==) printf("%d\n",getkth(x));
else if (opt==) Insert(x),printf("%d\n",data[getpre(x)]),Delete(x);
else Insert(x),printf("%d\n",data[getsuc(x)]),Delete(x);
}
return ;
}

没有重复数字的情况:

getk和getkth函数

 // 只在没有重复数字是使用
inline int getk(int k) {
int p = Root,ans = ;
while (true) {
if (k == data[p]) {splay(p,);return ans+;}
if (k < data[p]) p = ch[p][];
else {
ans += (ch[p][] ? siz[ch[p][]] : ) + ;
p = ch[p][];
}
}
}
inline int getkth(int k) {
int p = Root;
while (true) {
if (k == siz[ch[p][]]+) return p;
if (ch[p][] && k <= siz[ch[p][]]) p = ch[p][];
else {
k -= ((ch[p][] ? siz[ch[p][]] : ) + );
p = ch[p][];
}
}
}

insert,delete

 inline void Insert(int x) {
if (Root==) {
++tn;Root = tn;
ch[tn][] = ch[tn][] = fa[tn] = ;
siz[tn] = ;data[tn] = x;
return ;
}
int p = Root,pa = ;
while (true) {
pa = p;
p = ch[p][x > data[p]];
if (p==) {
++tn;
ch[tn][] = ch[tn][] = ;fa[tn] = pa;
ch[pa][x > data[pa]] = tn;
siz[tn] = ;data[tn] = x;
pushup(pa),splay(tn,);break;
}
}
}
inline void Clear(int x) {
ch[x][] = ch[x][] = fa[x] = siz[x] = data[x] = ;
}
inline void Delete(int x) {
getk(x);
if (!ch[Root][] && !ch[Root][]) { Clear(Root);Root = ;return;}
if (!ch[Root][]) {
int tmp = Root;Root = ch[Root][];fa[Root] = ;Clear(tmp);return;
}
else if (!ch[Root][]) {
int tmp = Root;Root = ch[Root][];fa[Root] = ;Clear(tmp);return;
}
int tmp = Root,pre = ch[Root][];
while (ch[pre][]) pre = ch[pre][];
splay(pre,);
ch[Root][] = ch[tmp][];
fa[ch[tmp][]] = Root;
Clear(tmp);
pushup(Root);
}

查找大于等于x的数或者小于等于:

getpre和getsuc函数

 //这两个函数可以等于查找的数
inline int getpre(int x) { // 返回第一个小于等于x的数
int p = Root,ans = ;
while (p) {
if (x < data[p]) p = ch[p][];
else ans = p,p = ch[p][];
}
return ans;
}
inline int getsuc(int x) { // 返回第一个大于等于x的数
int p = Root,ans = ;
while (p) {
if (x > data[p]) p = ch[p][];
else ans = p,p = ch[p][];
}
}

getpre,getsuc函数另一种操作:

getpre(x):找x的前驱,首先找到x的排名k = getk(x),然后求出排名为k-1的数:pre=getkth(k-1);

getsuc同理

最新文章

  1. Android 如何有效的解决内存泄漏的问题
  2. ASP.NET SignalR 与 LayIM2.0 配合轻松实现Web聊天室(七) 之 历史记录查询(时间,关键字,图片,文件),关键字高亮显示。
  3. JfreeChart的使用
  4. WebSocket 服务器3
  5. 根据CSV找出USBGroup中计算机对应的用户
  6. MyBatis插入多条
  7. Appnium移动自动化框架初探
  8. mybatis 自动生成xml文件配置
  9. Android定位功能
  10. 康复计划#1 再探后缀自动机&amp;后缀树
  11. rabbitmq之确保消息不丢失
  12. 五、latex文档的篇章结构
  13. squid代理http和https方式上网的操作记录
  14. 20165336 2017-2018-2《Java程序设计》第6周学习总结
  15. ssh 中 远程文件传输
  16. String 类 常用函数
  17. 十三、jdk命令之Java内存之本地内存分析神器:NMT 和 pmap
  18. com.mysql.jdbc.exceptions.jdbc4.MySQLSyntaxErrorException: Unknown character set: 'utf8mb4'
  19. 十三、Node.js-fs模块(上)
  20. Sublime Text 3预览Markdown

热门文章

  1. Java 多线程概念
  2. P3818 小A和uim之大逃离 II
  3. Error: EPERM: operation not permitted,
  4. 【Python图像特征的音乐序列生成】一个更科学的图片分类参考方法,以及一个看起来很好用的数据集
  5. ucos-ii核心算法分析(转)
  6. MVC web api转换JSON 的方法
  7. 【转】Deactivating your reflector
  8. 第011课_串口(UART)的使用
  9. webpack配置指南
  10. nodejs安装遇到npm命令无法使用问题