学习自: https://www.luogu.org/blog/user28084/solution-p3369
简述: 看了一个下午 + 晚上搞出来的东西.
题目:
您需要写一种数据结构(可参考题目标题), 来维护一些数, 其中需要提供以下操作:
插入 x 数;
删除 x 数(若有多个相同的数, 因只删除一个);
查询 x 数的排名(若有多个相同的数, 因输出最小的排名);
查询排名为 x 的数;
求 x 的前趋(前趋定义为小于 x , 且最大的数);
求 x 的后继(后继定义为大于 x , 且最小的数).
解题报告: 代码即解释.
- /* 替罪羊树
- 您需要写一种数据结构(可参考题目标题), 来维护一些数, 其中需要提供以下操作:
- 1. 插入 x 数;
- 2. 删除 x 数(若有多个相同的数, 因只删除一个);
- 3. 查询 x 数的排名(若有多个相同的数, 因输出最小的排名);
- 4. 查询排名为 x 的数;
- 5. 求 x 的前趋(前趋定义为小于 x , 且最大的数);
- 6. 求 x 的后继(后继定义为大于 x , 且最小的数).*/
- #include<bits/stdc++.h>
- #define numm ch-48
- #define pd putchar(' ')
- #define pn putchar('\n')
- #define pb push_back
- #define debug(args...) cout<<#args<<"->"<<args<<endl
- #define bug cout<<"************"
- using namespace std;
- template <typename T>
- void read(T &res) {
- bool flag=false;char ch;
- while(!isdigit(ch=getchar())) (ch=='-')&&(flag=true);
- for(res=numm;isdigit(ch=getchar());res=(res<<1)+(res<<3)+numm);
- flag&&(res=-res);
- }
- template <typename T>
- void write(T x) {
- if(x<0) putchar('-'),x=-x;
- if(x>9) write(x/10);
- putchar(x%10+'0');
- }
- typedef long long ll;
- typedef long double ld;
- const int maxn=2e5+10;
- const ll mod=1e9+7;
- const int inf=0x3f3f3f3f;
- const double alpha=0.7;
- #define il inline
- struct node {
- int exist,son[2],sze,valid,val;
- ///valid: 当前子树的真实大小
- ///sze: 当前子树的虚假大小
- ///exist: 当前节点是否存在
- ///val: 当前节点的权值
- ///son[0]: 左儿子, son[1]: 右儿子
- }e[maxn];
- int memory[maxn],cur[maxn],mpos,cpos,to_rebuild,root;
- ///memory[]: 内存池(下标 mpos);cur[]: 存放要重建的树的中序遍历(下标 cpos)
- il bool isbad(int now) { /// 以当前节点为根的子树是否需要重建
- if((double)e[now].valid*alpha<=(double)max(e[e[now].son[0]].valid,e[e[now].son[1]].valid))
- return true; /// 需要重建
- else return false;
- }
- il void build(int l,int r,int &now) {/// 对有序序列进行重构二叉树
- int mid=l+r>>1;
- now=cur[mid]; /// 每次都相当于把中间这个数提出来
- if(l==r) {
- e[now].son[0]=e[now].son[1]=0;
- e[now].valid=e[now].sze=1;
- return ;
- }
- if(l<mid) build(l,mid-1,e[now].son[0]); ///mid 这个结点已经建完了
- else e[now].son[0]=0;
- build(mid+1,r,e[now].son[1]);/// 这里为什么不用判呢? 想一下 l=3,r=4 的情况
- e[now].sze=e[e[now].son[0]].sze+e[e[now].son[1]].sze+1; ///+1 要划重点!!!
- e[now].valid=e[e[now].son[0]].valid+e[e[now].son[1]].valid+1;///+1 就是加本身
- return ;
- }
- il void dfs(int now) { /// 求中序遍历
- if(!now) return ;
- dfs(e[now].son[0]); /// 中序遍历先遍历左子树
- if(e[now].exist) cur[++cpos]=now;/// 存在的结点压入 cur
- else memory[++mpos]=now;/// 不存在的则回收
- dfs(e[now].son[1]);
- return ;
- }
- il void rebuild(int &now) {/// 重建二叉树
- cpos=0; ///attention!!!
- dfs(now);
- if(cpos) build(1,cpos,now);
- else now=0; /// 没有要重建的, now=0
- }
- il void ins(int &now,int val) { /// 插入一个数
- if(!now) {
- now=memory[mpos--]; /// 分配一个空间给当前结点, 作为它的下标
- e[now].val=val;
- e[now].exist=e[now].valid=e[now].sze=1;
- e[now].son[0]=e[now].son[1]=0;
- return ;
- }
- e[now].sze++,e[now].valid++;
- if(val<=e[now].val) ins(e[now].son[0],val);/// 比当前的值大往右, 否则往左
- else ins(e[now].son[1],val);
- if(!isbad(now)) { /// 如果回溯到当前节点不用重建, 就判断在它之前回溯的是否有需要重建的
- if(to_rebuild) {
- if(to_rebuild==e[now].son[0]) rebuild(e[now].son[0]);/// 判断左右子树哪个需要重建
- else rebuild(e[now].son[1]);
- to_rebuild=0;
- }
- }
- else to_rebuild=now;/// 当前节点需要重建, 先不重建, 继续回溯
- }
- il int find_rnk(int val) {/// 查找权值为 val 对应的排名
- int ans=1,now=root;
- while(now) {
- if(e[now].val>=val) now=e[now].son[0];
- else { /// 下面两句话不要写颠倒!!!
- ans+=e[e[now].son[0]].valid+e[now].exist;
- now=e[now].son[1];
- }
- }
- return ans;
- }
- il int find_val(int k) { /// 查找排名为 k 对应的权值
- int now=root;
- while(now) {
- if(e[now].exist&&e[e[now].son[0]].valid+1==k) return e[now].val;
- if(e[e[now].son[0]].valid>=k) now=e[now].son[0];
- else { /// 下面两句话不要写颠倒!!!
- k=k-e[e[now].son[0]].valid-e[now].exist;
- now=e[now].son[1];
- }
- }
- }
- il void del_rnk(int &now,int k) { /// 删除排名为 k 的结点
- if(e[now].exist&&e[e[now].son[0]].valid+1==k) {/// 当前的 now 为要找的结点
- e[now].exist=0;
- e[now].valid--;
- return ;
- }
- e[now].valid--;
- if(e[e[now].son[0]].valid+e[now].exist>=k) del_rnk(e[now].son[0],k);
- else del_rnk(e[now].son[1],k-e[e[now].son[0]].valid-e[now].exist);
- return ;
- }
- il void del_val(int val) { /// 删除权值为 val 的数(删除靠左的第一个数)
- del_rnk(root,find_rnk(val));
- if((double)e[root].sze*alpha>(double)e[root].valid) rebuild(root); /// 如果删除的结点太多, 则也需要重建
- }
- int main()
- {
- int n,op,val;
- for(int i=1;i<=maxn-1;i++)
- memory[i]=i;
- while(scanf("%d",&n)!=EOF) {
- root=to_rebuild=0;
- e[0].valid=0;
- mpos=(int)2e5-1; /// 内存池下标初始化
- for(int i=1;i<=n;i++) {
- read(op);read(val);
- if(op==1)
- ins(root,val);
- else if(op==2)
- del_val(val);
- else if(op==3)
- write(find_rnk(val)),pn;
- else if(op==4)
- write(find_val(val)),pn;
- else if(op==5)
- write(find_val(find_rnk(val)-1)),pn;
- ///find_rnk 总会找到 val 最小的 rnk,-1 就是最后一个比它小的数的 rnk
- else if(op==6)
- write(find_val(find_rnk(val+1))),pn;
- /// 找到比 val 小 (包括 val) 的数的数量, 直接查找该 rnk 对应的 val
- }
- pn;
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3265940.html