BZOJ 3224: Tyvj 1728 普通平衡树

正文索引 [隐藏]

Input
Output
Sample Input
Sample Output
HINT
题解
代码

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.每个数的数据范围：[-1e7,1e7]

题解

一个平衡树模版题、、Orz我手残复制了多项式忘记改符号了、对拍拍得我都要死了……
一棵treap是一棵修改了结点顺序的二叉查找树，如图，显示一个例子，通常树内的每个结点x都有一个关键字值key[x]，另外，还要为结点分配priority[x]，它是一个独立选取的随机数。
假设所有的优先级是不同的，所有的关键字也是不同的。treap的结点排列成让关键字遵循二叉查找树性质，并且优先级遵循最小堆顺序性质：
1.如果v是u的左孩子，则key[v] < key[u].
2.如果v是u的右孩子，则key[v] > key[u].
3.如果v是u的孩子，则priority[u] > priority[u].
这两个性质的结合就是为什么这种树被称为“treap”的原因，因为它同时具有二叉查找树和堆的特征。

用以下方式考虑treap会有帮助。假设插入关联关键字的结点x1，x2，…，xn到一棵treap内。结果的treap是将这些结点以它们的优先级(随机选取)的顺序插入一棵正常的二叉查找树形成的，亦即priority[xi] < priority[xj]表示xi在xj之前被插入。
在算法导论的12.4节中，其证明了随机构造的二叉查找树的期望高度为O(lgn)，因而treap的期望高度亦是O(lgn)。
treap插入操作：
1.按照二叉树的插入方法，将结点插入到树中
2.根据堆的性质(我们这里为最小堆)和优先级的大小调整结点位置。
treap删除操作：
1.找到相应的结点
2.若该结点为叶子结点，则直接删除；
若该结点为只包含一个叶子结点的结点，则将其叶子结点赋值给它；
若该结点为其他情况下的节点，则进行相应的旋转，直到该结点为上述情况之一，然后进行删除。
旋转主要涉及到右旋转的左旋转，下面把右旋转的图画在下面：

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int Maxn=100015;
struct Btree{
    int wei,val,siz;
    int rnd;
    int left,right;
    Btree(){left=right=0;}
    Btree(int wei0,int val0,int siz0,int rnd0){
        wei=wei0;
        val=val0;
        siz=siz0;
        rnd=rnd0;
        left=right=0;
    }
};
Btree tree[Maxn];
int nume;
inline void update(int x){
    tree[x].siz=tree[tree[x].left].siz+tree[tree[x].right].siz+tree[x].wei;
}
inline void leftTurn(int &x){
    int y=tree[x].right;
    tree[x].right=tree[y].left;
    tree[y].left=x;
    tree[y].siz=tree[x].siz;
    update(x);
    x=y;
}
inline void rightTurn(int &x){
    int y=tree[x].left;
    tree[x].left=tree[y].right;
    tree[y].right=x;
    tree[y].siz=tree[x].siz;
    update(x);
    x=y;
}
void insert(int &x,int v){
    if (x==0){
        nume++;
        x=nume;
        tree[x]=Btree(1,v,1,rand());
        return ;
    }
    tree[x].siz++;
    if (tree[x].val==v){
        tree[x].wei++;
        return ;
    }
    if (tree[x].val>v){
        insert(tree[x].left,v);
        if (tree[tree[x].left].rnd<tree[x].rnd) rightTurn(x);
    }else{
        insert(tree[x].right,v);
        if (tree[tree[x].right].rnd<tree[x].rnd) leftTurn(x);
    }
}
void del(int &x,int v){
    if (x==0) return ;
    if (tree[x].val==v){
        if (tree[x].wei>1){
            tree[x].wei--;
            tree[x].siz--;
            return;
        }
        if (tree[x].left*tree[x].right==0){
            x=tree[x].left+tree[x].right;
            return ;
        }
        if (tree[tree[x].left].rnd<tree[tree[x].right].rnd){
            rightTurn(x);
            del(x,v);
        }else{
            leftTurn(x);
            del(x,v);
        }
    }else{
        if (v<tree[x].val){
            tree[x].siz--;
            del(tree[x].left,v);
        }else{
            tree[x].siz--;
            del(tree[x].right,v);
        }
    }
}
int Ans;
int getRank(int x,int v){
    if (x==0) return 0;
    if (tree[x].val==v){
        return tree[tree[x].left].siz+1;
    }else{
        if (v<=tree[x].val){
            return getRank(tree[x].left,v);
        }else{
            return tree[tree[x].left].siz+tree[x].wei+getRank(tree[x].right,v);
        }
    }
}
int getNum(int x,int k){
    if (x==0) return 0;
    if (k<=tree[tree[x].left].siz)   return getNum(tree[x].left,k);
    if (tree[tree[x].left].siz+tree[x].wei<k) return getNum(tree[x].right,k-tree[tree[x].left].siz-tree[x].wei);
    return tree[x].val;
}
void getNxt(int x,int v){
    if (x==0) return ;
    if (tree[x].val<=v){
        getNxt(tree[x].right,v);
    }else{
        Ans=x;
        getNxt(tree[x].left,v);
    }
}
void getPrev(int x,int v){
    if (x==0) return;
    if (v<=tree[x].val){
        getPrev(tree[x].left,v);
    }else{
        Ans=x;
        getPrev(tree[x].right,v);
    }
}
int root,opt,n,val;
int main(){
    //freopen("3224.in","r",stdin);
    //freopen("3224.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d%d",&opt,&val);
        switch(opt){
            case 1:
                insert(root,val);
                break;
            case 2:
                del(root,val);
                break;
            case 3:
                printf("%dn",getRank(root,val));
                break;
            case 4:
                printf("%dn",getNum(root,val));
                break;
            case 5:
                Ans=0;
                getPrev(root,val);
                printf("%dn",tree[Ans].val);
                break;
            case 6:
                Ans=0;
                getNxt(root,val);
                printf("%dn",tree[Ans].val);
                break;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

#include<cstdio>

#include<algorithm>

using namespace std;

const int Maxn=100015;

struct Btree{

int wei,val,siz;

int rnd;

int left,right;

Btree(){left=right=0;}

Btree(int wei0,int val0,int siz0,int rnd0){

wei=wei0;

val=val0;

siz=siz0;

rnd=rnd0;

left=right=0;

}

};

Btree tree[Maxn];

int nume;

inline void update(int x){

tree[x].siz=tree[tree[x].left].siz+tree[tree[x].right].siz+tree[x].wei;

}

inline void leftTurn(int &x){

int y=tree[x].right;

tree[x].right=tree[y].left;

tree[y].left=x;

tree[y].siz=tree[x].siz;

update(x);

x=y;

}

inline void rightTurn(int &x){

int y=tree[x].left;

tree[x].left=tree[y].right;

tree[y].right=x;

tree[y].siz=tree[x].siz;

update(x);

x=y;

}

void insert(int &x,int v){

if (x==0){

nume++;

x=nume;

tree[x]=Btree(1,v,1,rand());

return ;

}

tree[x].siz++;

if (tree[x].val==v){

tree[x].wei++;

return ;

}

if (tree[x].val>v){

insert(tree[x].left,v);

if (tree[tree[x].left].rnd<tree[x].rnd) rightTurn(x);

}else{

insert(tree[x].right,v);

if (tree[tree[x].right].rnd<tree[x].rnd) leftTurn(x);

}

void del(int &x,int v){

if (x==0) return ;

if (tree[x].val==v){

if (tree[x].wei>1){

tree[x].wei--;

tree[x].siz--;

return;

}

if (tree[x].left*tree[x].right==0){

x=tree[x].left+tree[x].right;

return ;

}

if (tree[tree[x].left].rnd<tree[tree[x].right].rnd){

rightTurn(x);

del(x,v);

}else{

leftTurn(x);

del(x,v);

}

}else{

if (v<tree[x].val){

tree[x].siz--;

del(tree[x].left,v);

}else{

tree[x].siz--;

del(tree[x].right,v);

}

int Ans;

int getRank(int x,int v){

if (x==0) return 0;

if (tree[x].val==v){

return tree[tree[x].left].siz+1;

}else{

if (v<=tree[x].val){

return getRank(tree[x].left,v);

}else{

return tree[tree[x].left].siz+tree[x].wei+getRank(tree[x].right,v);

}

int getNum(int x,int k){

if (x==0) return 0;

if (k<=tree[tree[x].left].siz) return getNum(tree[x].left,k);

if (tree[tree[x].left].siz+tree[x].wei<k) return getNum(tree[x].right,k-tree[tree[x].left].siz-tree[x].wei);

return tree[x].val;

}

void getNxt(int x,int v){

if (x==0) return ;

if (tree[x].val<=v){

getNxt(tree[x].right,v);

}else{

Ans=x;

getNxt(tree[x].left,v);

}

void getPrev(int x,int v){

if (x==0) return;

if (v<=tree[x].val){

getPrev(tree[x].left,v);

}else{

Ans=x;

getPrev(tree[x].right,v);

}

int root,opt,n,val;

int main(){

//freopen("3224.in","r",stdin);

//freopen("3224.out","w",stdout);

scanf("%d",&n);

for (int i=1;i<=n;i++){

scanf("%d%d",&opt,&val);

switch(opt){

case 1:

insert(root,val);

break;

case 2:

del(root,val);

break;

case 3:

printf("%dn",getRank(root,val));

break;

case 4:

printf("%dn",getNum(root,val));

break;

case 5:

Ans=0;

getPrev(root,val);

printf("%dn",tree[Ans].val);

break;

case 6:

Ans=0;

getNxt(root,val);

printf("%dn",tree[Ans].val);

break;

}

return 0;

}

WNJXYKの博客

喂你脚下有坑