rockdu
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
插入x数
删除x数(若有多个相同的数，因只删除一个)
查询x数的排名(若有多个相同的数，因输出最小的排名)
查询排名为x的数
求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
输入输出格式
输入格式：
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
输出格式：
对于操作3,4,5,6每行输出一个数，表示对应答案
输入输出样例
输入样例#1：
10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598
输出样例#1：
106465 84185 492737
一道平衡树裸题。涉及很多常用的平衡树操作。但是刚刚接触平衡树，于是就调了一个很难看的Splay给AC了
基本思想：由于有重复数字，这里记一个cnt来存放节点中数的个数。
删除操作：将节点放在前驱节点和后继结点之间然后从后继节点断开（PS这里有一个小技巧，在空平衡树中插入inf和-inf就可以免去一堆特判）
查询排名：用一个push_up维护每个节点的size——子树大小。将节点旋转到根，左子树的size即比该数小的数的个数（注意：子树大小需要加上当前节点的cnt）
查询排名为X的数：从根节点出发，如果当前X在【左子树的size+1】到【左子树的size+cnt】之间，则找到并返回。否则分两种情况向下；
1：当前X>左子树size那么X-=（左子树size+当前cnt），向右继续向下；
2：否则向左继续向下；
那么，最后停下的点必定是原排名为X的节点；
求前驱后继：将当前节点旋转到根节点，从左节点开始一直向右找，一直到当前节点没有右儿子，当前节点为前驱，后继同理。
贴一段不太美观的代码
#include<cstdio>
using namespace std;
const int MAXN=1e5+100;
namespace Splay {
struct node {
int cnt,size,num,ch[2],fa;
void init() {cnt=size=num=ch[0]=ch[1]=fa=0;}
node() {init();}
void give(int rn,int rf,int rc,int rs) {num=rn;fa=rf;cnt=rc;size=rs;}
}tree[MAXN];
int cnt=0,root=0;
void push_up(int rt){
if(rt==0) return;//2?pushup0?úμ?
int l=tree[rt].ch[0];
int r=tree[rt].ch[1];
tree[rt].size=tree[l].size+tree[r].size+tree[rt].cnt;
}
void rotate(int rt){
int p=tree[rt].fa;
int a=tree[p].fa;
int l=tree[p].ch[1]==rt;
int r=l^1;
if(a)
if(tree[a].ch[0]==p) tree[a].ch[0]=rt;
else tree[a].ch[1]=rt;
tree[rt].fa=a,tree[p].fa=rt,tree[tree[rt].ch[r]].fa=tree[rt].ch[r]?p:0;
tree[p].ch[l]=tree[rt].ch[r],tree[rt].ch[r]=p;
push_up(p);
push_up(rt);
}
void splay(int now,int y){
int des=tree[y].fa;
while(des!=tree[now].fa){
int p=tree[now].fa;
int a=tree[p].fa;
if(p!=y)
if((tree[a].ch[0]==p)^(tree[p].ch[0]==now)) rotate(now);
else rotate(p);
rotate(now);
}
if(y==root) root=now;//??μ??üD??ù?úμ?
}
void insert(int & now,int x,int last){//?éò??üD??ù?úμ?
if(now==0){now=++cnt;tree[cnt].give(x,last,1,1);
tree[last].ch[tree[last].num<x]=now;splay(now,root);return;}
if(tree[now].num==x){tree[now].cnt++;tree[now].size++;splay(now,root);return;}
insert(tree[now].ch[tree[now].num<x],x,now);
//push_up(now);
}
int find(int num){
int now=root;
while(tree[now].num!=num && now)
now=tree[now].ch[tree[now].num<num];
if(!now) return -1;
return now;
}
int qnode(int now,bool type){ //type: 0:?°?y 1:oó?ì
splay(now,root);
int p=tree[now].ch[type];
if(!p) return -1;
while(tree[p].ch[type^1])
p=tree[p].ch[type^1];
return p;
}
int qrank(int num){
int now=find(num);
splay(now,root);
return tree[tree[now].ch[0]].size+1;
}
int qnum(int x){
int now=root;
while(x>tree[tree[now].ch[0]].size+tree[now].cnt || x<tree[tree[now].ch[0]].size+1){
int l=tree[now].ch[0];
int r=tree[now].ch[1];
if(tree[tree[now].ch[0]].size+tree[now].cnt<x)
x-=(tree[tree[now].ch[0]].size+tree[now].cnt),now=r;
else now=l;
}
return tree[now].num;
}
void del(int now){
tree[now].cnt--,tree[now].size--;
int p=tree[now].fa;
if(!tree[now].cnt){
int pr=qnode(now,0);
int su=qnode(now,1);
splay(pr,root);splay(su,tree[pr].ch[1]);
tree[su].ch[0]=0;
p=tree[now].fa;
tree[now].init();
}
while(p){
push_up(p);
p=tree[p].fa;
}
}
int qrn(int num,bool type){
insert(root,num,0);
int ans=qnode(root,type);
del(root);
return tree[ans].num;
}
}
int main(){
using namespace Splay;
int t;
scanf("%d",&t);
insert(root,2147483647,0);
insert(root,-2147483647,0);
while(t--){
int opt,x;
scanf("%d%d",&opt,&x);
if(opt==1) insert(root,x,0);
if(opt==2) del(find(x));
if(opt==3) printf("%d\n",qrank(x) - 1);
if(opt==4) printf("%d\n",qnum(x + 1));
if(opt==5) printf("%d\n",qrn(x,0));
if(opt==6)
printf("%d\n",qrn(x,1));
}
return 0;
}2017-12-23
学习了其他类型的平衡树，发现Splay常数非常大。这里给出Treap和替罪羊树的代码。
需要特别注意的是Treap的删除操作，很容易忘了特判根节点、在有多个权值时不删除节点。另外替罪羊树的删除是假删除（类似KDtree），对功能函数有一定的影响，不好写前驱后继，可以用查询第K大和查询X的排名来代（tou）替（lan）。
Treap:
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x7fffffff;
int Rand() {return rand() * 666 + rand();}
namespace Treap {
const int L = 0, R = 1;
struct node {
int ch[2], num, size, cnt, fa, key;
}tree[maxn];
int cnt, root;
void init() {srand(time(0)), tree[0].key = inf;}
void push_up(int rt) {
tree[rt].size = tree[tree[rt].ch[L]].size + tree[tree[rt].ch[R]].size + tree[rt].cnt;
}
void rotate(int rt) {
int p = tree[rt].fa, a = tree[p].fa;
int l = tree[p].ch[R] == rt, r = l ^ 1;//用全部是左儿子来想
if(a) tree[a].ch[tree[a].ch[R] == p] = rt;
tree[rt].fa = a, tree[p].fa = rt, tree[tree[rt].ch[r]].fa = p;
tree[p].ch[l] = tree[rt].ch[r], tree[rt].ch[r] = p;
push_up(p), push_up(rt);
}
void adjust(int rt) {
while(tree[rt].key < tree[tree[rt].fa].key) rotate(rt);
if(!tree[rt].fa) root = rt;
}
void insert(int & rt, int x, int last) {
if(!rt) rt = ++cnt, tree[rt] = (node) {0, 0, x, 1, 1, last, Rand()};
else {
if(tree[rt].num < x) insert(tree[rt].ch[R], x, rt);
else if(tree[rt].num > x) insert(tree[rt].ch[L], x, rt);
else ++tree[rt].cnt;
push_up(rt);
}
}
void Ins(int num) {insert(root, num, 0), adjust(cnt);}
void Up(int now) {while(now) push_up(now), now = tree[now].fa;}
int find(int num) {
int now = root;
for(; tree[now].num != num; now = tree[now].ch[tree[now].num < num]);
return now;
}
void del(int num) {
int now = find(num);
if(tree[now].cnt > 1) --tree[now].cnt, Up(now);
else {
int ls = tree[now].ch[L], rs = tree[now].ch[R];
if(now == root) {
if(!(ls * rs)) root = rs ? rs : ls;
else root = tree[ls].key < tree[rs].key ? rs : ls;
}
for(; ls | rs; ls = tree[now].ch[L], rs = tree[now].ch[R]) {
if(!(ls * rs)) rotate(rs ? rs : ls);
else rotate(tree[ls].key < tree[rs].key ? rs : ls);
}
int p = tree[now].fa;
tree[p].ch[tree[p].ch[R] == now] = 0, Up(p);
}
}
int qrank(int x, int & c) {
int now = root, num = tree[now].num, ans = 0;
for(; now; num = tree[now].num) {
if(num < x) ans += tree[tree[now].ch[L]].size + tree[now].cnt, now = tree[now].ch[R];
else if(num > x) now = tree[now].ch[L];
else return c = tree[now].cnt, ans + tree[tree[now].ch[L]].size;
}
return c = tree[now].cnt, ans;
}
int qnum(int rank) {
int tl = tree[root].ch[L], now = root;
for(;; tl = tree[now].ch[L]) {
if(tree[tl].size >= rank) now = tl;
else if(tree[tl].size + tree[now].cnt < rank)
rank -= tree[tl].size + tree[now].cnt, now = tree[now].ch[R];
else return tree[now].num;
}
}
}
int n, opt, a, b, c, tot;
int main() {
using namespace Treap;
init();
scanf("%d", &n);
while(n--) {
scanf("%d%d", &opt, &a);
if(opt == 1) Ins(a);
else if(opt == 2) del(a);
else if(opt == 3) printf("%d\n", qrank(a, c) + 1);
else if(opt == 4) printf("%d\n", qnum(a));
else if(opt == 5) printf("%d\n", qnum(qrank(a, c)));
else printf("%d\n", qnum(qrank(a, c) + c + 1));
}
return 0;
}
/* *注：可以用下面两个函数实现前驱和后继的查找，节省常数。
int pre(int rt, int num) {
if(!rt) return -inf;
if(tree[rt].num < num) return max(tree[rt].num, pre(tree[rt].ch[R], num));
else return pre(tree[rt].ch[L], num);
}
int suc(int rt, int num) {
if(!rt) return inf;
if(tree[rt].num > num) return min(tree[rt].num, suc(tree[rt].ch[L], num));
else return suc(tree[rt].ch[R], num);
}*/替罪羊树:
#include<cstdio>
#include<queue>
using namespace std;
const int maxn = 1e5 + 5, inf = 0x7fffffff;
const double per = 0.75;
namespace SBT {
const int L = 0, R = 1;
struct node {
int ch[2], size, cnt, num;
}tree[maxn];
int cnt, root = 1;
int num[maxn], tot[maxn], len;
queue<int > q;
int New() {
int ret = cnt + 1;
if(q.empty()) return ++cnt, ret;
else ret = q.front();
return q.pop(), ret;
}
void push_up(int rt) {
int tl = tree[rt].ch[L], tr = tree[rt].ch[R];
tree[rt].size = tree[tl].size + tree[tr].size + tree[rt].cnt;
}
int insert(int & rt, int & fa, const int &x, const int &last) {
if(!rt) {
rt = ++cnt, tree[rt] = (node) {0, 0, 1, 1, x};
return -1;
}
int ret = -1, *tr = &tree[rt].ch[R], *tl = &tree[rt].ch[L];
if(tree[rt].num < x) ret = insert(*tr, fa, x, rt);
else if(tree[rt].num > x) ret = insert(*tl, fa, x, rt);
else ++tree[rt].cnt;
push_up(rt);
if(tree[*tl].size * 1.0 > tree[rt].size * per) return fa = last, rt;
if(tree[*tr].size * 1.0 > tree[rt].size * per) return fa = last, rt;
return ret;
}
void Gettree(int rt) {
if(!rt) return;
Gettree(tree[rt].ch[L]);
num[++len] = tree[rt].num, tot[len] = tree[rt].cnt;
Gettree(tree[rt].ch[R]);
q.push(rt), tree[rt] = (node){0};
}
void Build(int l, int r, int & rt) {
rt = New();
int mid = l + r >> 1;
tree[rt].num = num[mid];
tree[rt].size = tree[rt].cnt = tot[mid];
if(l < mid) Build(l, mid - 1, tree[rt].ch[L]);
if(r > mid) Build(mid + 1, r, tree[rt].ch[R]);
push_up(rt);
}
void ReBuild(int rt, int fa) {
len = 0, Gettree(rt);
int Nrt = rt;
Build(1, len, Nrt);
tree[fa].ch[tree[fa].ch[R] == rt] = Nrt;
if(rt == root) root = Nrt;
}
int qnum(int rank) {
int tl = tree[root].ch[L], now;
for(now = root; now; tl = tree[now].ch[L]) {
if(tree[tl].size >= rank) now = tl;
else if(tree[tl].size + tree[now].cnt < rank)
rank -= tree[tl].size + tree[now].cnt, now = tree[now].ch[R];
else return tree[now].num;
}
return tree[now].num;
}
int qrank(int x, int & c) {
int num = tree[root].num, ans = 0, now;
c = 0;
for(now = root; now; num = tree[now].num) {
if(tree[now].num < x) {
ans += tree[tree[now].ch[L]].size;
ans += tree[now].cnt;
now = tree[now].ch[R];
}else if(tree[now].num > x) now = tree[now].ch[L];
else {
ans += tree[tree[now].ch[L]].size;
c = tree[now].cnt;
break;
}
}
return ans;
}
void del(int rt, int x) {
if(tree[rt].num == x) {--tree[rt].cnt, --tree[rt].size;return;}
del(tree[rt].ch[tree[rt].num < x], x);
push_up(rt);
}
}
int n, opt, a, rec, rt, c;
int main() {
using namespace SBT;
//freopen("test.out", "w", stdout);
scanf("%d", &n);
SBT::insert(a, opt, inf, 0);
while(n--) {
scanf("%d%d", &opt, &a);
if(opt == 1) {
rt = insert(root, rec, a, 0);
if(~rt) ReBuild(rt, rec);
}else if(opt == 2) del(root, a);
else if(opt == 3) printf("%d\n", qrank(a, c) + 1);
else if(opt == 4) printf("%d\n", qnum(a));
else if(opt == 5) printf("%d\n", qnum(qrank(a, c)));
else printf("%d\n", qnum(rec = qrank(a, c) + c + 1));
}
return 0;
}
没有帐号? 立即注册