本文主要是介绍HDU 4585 Shaolin Splay 寻找前驱后继,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4585
每次添加一个数在集合中,并寻找这个数在集合排序后的前驱和后继
Splay模板题
每次将节点插入后 查找根左子树最右节点 和 根右子树最左节点
代码:
#include <bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
const int maxn = 100000 + 50,INF = 0x7fffffff;
/** ---- SPLAY ---- **/
int ch[maxn][2],fa[maxn],size[maxn];
int key[maxn],pos[maxn];
int tot,root,sroot;
void Splay_Init(){tot = 1;root = sroot = 0;ch[0][0] = ch[0][1] = 0;fa[0] = 0;key[0] = INF;size[0] = 0;
}
int NewNode(int FA,int k,int p){ch[tot][0] = ch[tot][1] = 0;fa[tot] = FA;size[tot] = 1;key[tot] = k,pos[tot] = p;return tot++;
}
void PushUp(int rt){size[rt] = 1 + size[ch[rt][0]] + size[ch[rt][1]];}
void rotate(int rt,int kind){int prt = fa[rt];ch[prt][kind] = ch[rt][!kind];fa[ch[rt][!kind]] = prt;ch[fa[prt]][ch[fa[prt]][1] == prt] = rt;fa[rt] = fa[prt];ch[rt][!kind] = prt;fa[prt] = rt;PushUp(prt);PushUp(rt);
}
void Splay(int rt,int goal){while(fa[rt] != goal){if(fa[fa[rt]] == goal) rotate(rt,ch[fa[rt]][1] == rt);else{int prt = fa[rt],kind = (ch[fa[prt]][1] == prt);if(ch[prt][kind] == rt) rotate(rt,kind),rotate(rt,kind);else rotate(rt,!kind),rotate(rt,kind);}}if(fa[rt] == sroot) root = rt;
}
void Insert(int rt,int k,int p){while(ch[rt][k > key[rt]]) rt = ch[rt][k > key[rt]];rt = (ch[rt][k > key[rt]] = NewNode(rt,k,p));Splay(rt,sroot);
}
int Find(int rt,int k){while(ch[rt][k >= key[rt]])if(k == key[rt]) return rt;else rt = ch[rt][k >= key[rt]];return sroot;
}
int Find_Pre(int rt,int k){rt = Find(rt,k);Splay(rt,sroot);if(ch[rt][0] == sroot) return sroot;else rt = ch[rt][0];while(ch[rt][1]) rt = ch[rt][1];return rt;
}
int Find_Next(int rt,int k){rt = Find(rt,k);Splay(rt,sroot);if(ch[rt][1] == sroot) return sroot;else rt = ch[rt][1];while(ch[rt][0]) rt = ch[rt][0];return rt;
}int main(){int n;while( ~sf("%d",&n) && n ){int x,y,u,d;Splay_Init();Insert(root,(int)1e9,1);while(n--){sf("%d%d",&x,&y);Insert(root,y,x);u = Find_Next(root,y);d = Find_Pre(root,y);if(u == sroot) pf("%d %d\n",x,pos[d]);else if(d == sroot) pf("%d %d\n",x,pos[u]);else {if(key[u] - y < y - key[d]) pf("%d %d\n",x,pos[u]);else pf("%d %d\n",x,pos[d]);}}}return 0;
}
这篇关于HDU 4585 Shaolin Splay 寻找前驱后继的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!