treap==tree+heap，二叉搜索树（BST）+大根堆
1.Binary search tree (BST) 二叉搜索树
满足条件：
一般看BST的中序遍历：1 2 3 4 5 6 7 8 9
一般的操作：
前面四个操作set就可以自己实现，其中6跟7的数可能在树中不存在，而3跟4找的数一定存在
heap的操作就是让BST尽量随机，使得期望值最高
涉及两个操作左旋跟右旋：
交换子节点跟父节点，操作完后的中序遍历不变 ，任然等于AyBxC
1.普通平衡树
#include<bits/stdc++.h> using namespace std; const int N=100010,INF=1e8; int n; struct Node { int l,r;//左右子节点 int key,val;//key存值，val存heap的随机值值 int cnt,size;//cnt记录key的个数，size表示子树的总共的树包括自己 }tr[N]; int root,idx;//相当于链表一样，root是节点，idx是开辟空间 void pushup(int p)//子节点更新父节点信息 { tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;//等于两个子节点的数+自己的数 } int get_node(int key)//添加一个新的节点 { tr[++idx].key=key; tr[idx].val=rand(); tr[idx].size=tr[idx].cnt=1; return idx; } void built()//建立链表 { get_node(-INF),get_node(INF);//建立一个负无穷与正无穷，防止有边界问题 root=1,tr[1].r=2;//根节点为1，根节点的右节点是2 pushup(root);//更新一下根节点 } void zig(int &p)//右旋，按照图进行操作 { int q=tr[p].l;//先q指针指向左节点这个位置 tr[p].l=tr[q].r,tr[q].r=p,p=q;//进行更换 pushup(tr[p].r),pushup(p);//更新一下节点信息 } void zag(int &p)//左旋 { int q=tr[p].r;//先q指针指向右节点这个位置 tr[p].r=tr[q].l,tr[q].l=p,p=q;//进行更换 pushup(tr[p].l),pushup(p););//更新一下节点信息 } void insert(int &p,int key)//插入一个值 { if(!p) p=get_node(key);//假如不存在，则添加一个节点 else if(tr[p].key==key) tr[p].cnt++;//假如有相同的，则cnt++ else if(tr[p].key>key)//假如在左边 { insert(tr[p].l,key);//则继续插入左边里 if(tr[tr[p].l].val>tr[p].val) zig(p);//假如插入后值改变了，则右旋一下 } else { insert(tr[p].r,key);//反之插入在右边 if(tr[tr[p].r].val>tr[p].val) zag(p);//假如值变大了，则左旋一下 } pushup(p);//更新一下节点信息 } void remove(int &p,int key)//删除一个key的值 { if(!p) return;//假如不存在 if(tr[p].key==key)//假如有相同的 { if(tr[p].cnt>1) tr[p].cnt--;//假如有多，则直接-- else if(tr[p].l||tr[p].r)//假如不是叶节点 { if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)//假如右节点空或者左边的价值大于右边的 { zig(p);//右旋把左节点换上去 remove(tr[p].r,key);//删除右节点 } else { zag(p);//把右节点换上去 remove(tr[p].l,key);//删除左节点 } } else p=0;//假如是跟节点，直接为0即可 } else if(tr[p].key>key) remove(tr[p].l,key);//假如在左边 else remove(tr[p].r,key);//假如在右边 pushup(p);//更新一下节点信息 } int get_rank_by_key(int p,int key)//通过数值找排名 { if(!p) return 0;//本题中不会发生这种情况 if(tr[p].key==key) return tr[tr[p].l].size+1;//假如找到了，则等于左边+1 if(tr[p].key>key) return get_rank_by_key(tr[p].l,key);//假如在左边 return tr[tr[p].l].size+tr[p].cnt+get_rank_by_key(tr[p].r,key);//假如在右边 } int get_key_by_rank(int p,int rank)//通过排名找数值 { if(!p) return INF;//本题中不会发生这种情况 if(tr[tr[p].l].size>=rank) return get_key_by_rank(tr[p].l,rank);//假如在左边 if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].key;//假如就是这个节点 return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);//反之，找右边的排名 } int get_prev(int p,int key)//找到严格小于key的最大值 { if(!p) return -INF; if(tr[p].key>=key) return get_prev(tr[p].l,key);//假如在左边 return max(tr[p].key,get_prev(tr[p].r,key));//反之自己或者右边取最大 } int get_next(int p,int key)//找到严格大于key的最小值 { if(!p) return INF; if(tr[p].key<=key) return get_next(tr[p].r,key);//假如在右边 return min(tr[p].key,get_next(tr[p].l,key));//反之自己或者左边的最小值 } int main() { built(); scanf("%d",&n); while(n--) { int opt,x; scanf("%d%d",&opt,&x); if(opt==1) insert(root,x);// else if(opt==2) remove(root,x); else if(opt==3) printf("%d\n",get_rank_by_key(root,x)-1);//因为有个负无穷的节点则节点位置要-1 else if(opt==4) printf("%d\n",get_key_by_rank(root,x+1));//因为有个负无穷的节点则节点位置要+1 else if(opt==5) printf("%d\n",get_prev(root,x)); else printf("%d\n",get_next(root,x)); } return 0; }
2.营业额统计
相似的题：邻值查找
题意：在前i个数找到与ai最近的数
则转换为1.找到大于等于ai的最小数2.找到小于等于ai的最大数，然后要最接近的数即可，也即平衡树的两个基本操作找前驱跟后继，这题用set也可以直接过
lower_bound：大于某个数的最小数
upper_bound：找到大于等于某个数的最小数，然后在--就是这个数的前驱，就找到小于等于某个数的最大数了
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=33000,INF=1e7; int n; int root,idx;//相当于链表的位置 struct Node { int l,r; int key,val; }tr[N]; int get_node(int key)//插入一个节点 { tr[++idx].key=key; tr[idx].val=rand(); return idx; } void built()//建立两个正无穷与负无穷节点 { get_node(-INF),get_node(INF); root=1,tr[1].r=2; } void zig(int &p)//右旋 { int q=tr[p].l; tr[p].l=tr[q].r,tr[q].r=p,p=q; } void zag(int &p)//左旋 { int q=tr[p].r; tr[p].r=tr[q].l,tr[q].l=p,p=q; } void insert(int &p,int key)//插入一个key的节点 { if(!p) p=get_node(key);//假如不存在这个节点，开辟一个 else if(tr[p].key==key) return;//假如已经存在了 else if(tr[p].key>key)//假如在左边 { insert(tr[p].l,key);//则插入在左边 if(tr[tr[p].l].val>tr[p].val) zig(p);//假如值变大了，则右旋一下 } else { insert(tr[p].r,key);//反之插入在右边 if(tr[tr[p].r].val>tr[p].val) zag(p);//假如值变大了，则左旋一下 } } int get_prev(int p,int key)//获取小于等于key的最大值 { if(!p) return -INF; if(tr[p].key>key) return get_prev(tr[p].l,key);//假如在左边 return max(tr[p].key,get_prev(tr[p].r,key));//假如在右边跟自己取最大 } int get_next(int p,int key)//获取大于等于key的最小值 { if(!p) return INF; if(tr[p].key<key) return get_next(tr[p].r,key);//假如在右边 return min(tr[p].key,get_next(tr[p].l,key));//假如在左边跟自己取最小 } int main() { ll res=0; built();//建立空结点 scanf("%d",&n); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); if(i==1) res+=x; else res+=min(x-get_prev(root,x),get_next(root,x)-x);//取最小 insert(root,x); } printf("%lld\n",res); return 0; }
stl中set的做法
#include<bits/stdc++.h> using namespace std; const int N=33000,INF=1e7; set<int>s; set<int>::iterator k,a;//set的两个迭代器 int n; int main() { int ans=0; s.insert(-INF),s.insert(INF);//插入两个正无穷和负无穷节点 scanf("%d",&n); for(int i=1;i<=n;i++) { int x; scanf("%d",&x); if(i==1) ans+=x; else { k=s.lower_bound(x);//获取大于等于x的第一个数 a=k; a--;//a是小于等于x的第一个数 ans+=min(x-*a,*k-x);//取两边最小 } s.insert(x); } printf("%d\n",ans); return 0; }
