首页 > 代码库 > BZOJ1588 营业额统计 splay tree
BZOJ1588 营业额统计 splay tree
最基本的平衡树操作吧,第一次学splay的可以做一下
只需要插入,删除,旋转,求前驱,后继这5个操作吧
不喜欢用指针,用数组写的
<span style="color:#00cccc;">//HNOI2002营业额统计 #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define INF 1<<30 #define N 100005 using namespace std; int pre[N],key[N],ch[N][2],root,tot,n; // 分别表示 父节点 、键值、左右子节点(0为左孩子,1为右孩子) 、根节点 、节点数目 void Newnode(int &p,int fa,int keyy) //新建一个节点 { p=++tot; pre[p]=fa; key[p]=keyy; ch[p][0]=ch[p][1]=0; } void Rotate(int x, int kind)//k为1时右旋, k为0时左旋 { int y=pre[x]; ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if (pre[y])//如果父节点不是根结点,则要和父节点的父节点连接起来 ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; } void Splay(int r,int goal)////Splay调整,将根为r的子树调整为goal { while (pre[r]!=goal) { if (pre[pre[r]]==goal)//父节点即是目标位置,goal为0表示,父节点就是根结点 Rotate(r,ch[pre[r]][0]==r); else { int y=pre[r]; int kind=ch[pre[y]][0]==y; if (ch[y][kind]==r) { Rotate(r,!kind); Rotate(r,kind); } else { Rotate(y,kind); Rotate(r,kind); } } } if (goal==0) root=r; } int Insert(int k) { while (ch[root][key[root]<k]) { if (key[root]==k) { Splay(root,0); return 0; } root=ch[root][key[root]<k]; } Newnode(ch[root][k>key[root]],root,k); Splay(ch[root][k>key[root]],0); return 1; } int get_pre(int x) { int tmp=ch[x][0]; if (tmp==0) return INF; while (ch[tmp][1]) tmp=ch[tmp][1]; return key[tmp]; } int get_next(int x) { int tmp=ch[x][1]; if (tmp==0) return INF; while (ch[tmp][0]) tmp=ch[tmp][0]; return key[tmp]; } int main() { while (scanf("%d",&n)!=EOF) { root=tot=0; int ans=0; for (int i=1; i<=n; i++) { int num; if (scanf("%d",&num)==EOF) num=0; if (i==1) { ans+=num; Newnode(root,0,num); continue; } if (Insert(num)==0) continue; int a=get_next(root); int b=get_pre(root); ans+=min(abs(a-key[root]),abs(key[root]-b)); } printf("%d",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。