插入 \(x\)：将根以 \(x\) 值分裂，在中间建一个新的点合并回去即可，比较容易 。删除 \(x\)：将根分别以 \(x-1,x\) 分裂，中间一个树就是权值为 \(x\) 的树，把这个树替换为它左右子树合并的结果即可（因为只要删一个，相当于把根节点给删了 。查询 \(x\) 的排名：这个非常容易，直接按 \(x-1\) 分裂并输出第一个子树大小 +1 即可 。查询排名为 \(x\) 的数：这个可以从根节点开始，不停地判断应该往左子树走还是右子树走，判断方式就是看当前点地左子树大小 +1 和 \(x\) 的大小关系，若相等则直接退出 。**查询 \(x\) 的前驱：$$笔者做法比较暴力，直接将数按 \(x-1\) 分裂，第一棵树的最后一个就是，最后一个求可以查询排名为数大小的数，用之前的函数可以求出 。**查询 \(x\) 的后继：$$同前驱做法，按 \(x\) 分裂，第二棵树的第一个就是，同样查询排名为 1 的树即可，使用之前的函数 。
具体的还是看代码吧 。
#include <bits/stdc++.h>#define TIME 1e3*clock()/CLOCKS_PER_SECusing namespace std;// stay organizedmt19937 rnd(233);const int maxn=1e5+10;struct Node{int ls,rs;int siz;int val,key;}tree[maxn];int rt=0,tot=0;int newnode(int val){tot++;tree[tot].ls=tree[tot].rs=0;tree[tot].siz=1;tree[tot].val=val;tree[tot].key=rnd();return tot;}void upd(int x){tree[x].siz=tree[tree[x].ls].siz+1+tree[tree[x].rs].siz;}void split(int cur,int k,int &x,int &y){if(!cur){x=y=0;return;}if(tree[cur].val<=k){x=cur;split(tree[x].rs,k,tree[x].rs,y);}else{y=cur;split(tree[y].ls,k,x,tree[y].ls);}upd(cur);}int merge(int x,int y){if(!x||!y)return x+y;if(tree[x].key>=tree[y].key){tree[x].rs=merge(tree[x].rs,y);upd(x);return x;}else{tree[y].ls=merge(x,tree[y].ls);upd(y);return y;}}int x,y,z;void ins(int val){split(rt,val,x,y);rt=merge(merge(x,newnode(val)),y);}void del(int val){split(rt,val-1,x,y);split(y,val,y,z);y=merge(tree[y].ls,tree[y].rs);rt=merge(merge(x,y),z);}int rnk(int val){split(rt,val-1,x,y);int ans=tree[x].siz+1;rt=merge(x,y);return ans;}int kth(int now,int k){while(tree[tree[now].ls].siz+1!=k){if(tree[tree[now].ls].siz+1>k)now=tree[now].ls;else{k-=tree[tree[now].ls].siz+1;now=tree[now].rs;}}return tree[now].val;}int pre(int val){split(rt,val-1,x,y);int ans=kth(x,tree[x].siz);rt=merge(x,y);return ans;}int suf(int val){split(rt,val,x,y);int ans=kth(y,1);rt=merge(x,y);return ans;}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cin>>t;int opt,x;while(t--){cin>>opt>>x;if(opt==1)ins(x);else if(opt==2)del(x);else if(opt==3)cout<<rnk(x)<<'\n';else if(opt==4)cout<<kth(rt,x)<<'\n';else if(opt==5)cout<<pre(x)<<'\n';else cout<<suf(x)<<'\n';}return 0;// you should actually read the stuff at the bottom}/* stuff you should look for* int overflow, array bounds* clear the arrays?* special cases (n=1?),* WRITE STUFF DOWN,* DON'T GET STUCK ON ONE APPROACH*/
经验总结扩展阅读
- 一 UBOOT编译--- make xxx_deconfig过程详解
- 图文超详解 G1 垃圾收集器深入剖析
- 小米电视4a和4c哪个好 两者区别详解
- 等离子电视机好还是液晶电视机好 两者的区别详解
- 等离子电视机出故障怎么办 维修方法详解
- 图文全面详解 Kafka 架构和原理机制
- FlinkSql之TableAPI详解
- 水瓶座2023年7月财运 水瓶座2023年7月运势详解完整版
- 水瓶座2023年7月运势完整版 水瓶座2023年7月运势详解
- [Pyhton] SimPy 离散事件模拟框架详解 —— 以一个简单的汽车充电排队模拟为例