可以下载各种软件的网站,wap是什么意思卡迪碧,德国的网站域名,宿迁宿豫网站建设题干#xff1a;
您需要写一种数据结构#xff08;可参考题目标题#xff09;#xff0c;来维护一些数#xff0c;其中需要提供以下操作#xff1a; 1. 插入x数 2. 删除x数(若有多个相同的数#xff0c;因只删除一个) 3. 查询x数的排名(若有多个相同的数#xff0c;因…题干
您需要写一种数据结构可参考题目标题来维护一些数其中需要提供以下操作 1. 插入x数 2. 删除x数(若有多个相同的数因只删除一个) 3. 查询x数的排名(若有多个相同的数因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x且最大的数) 6. 求x的后继(后继定义为大于x且最小的数)
Input
第一行为n表示操作的个数,下面n行每行有两个数opt和xopt表示操作的序号(1opt6)
Output
对于操作3,4,5,6每行输出一个数表示对应答案
Sample Input
10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598
Sample Output
106465 84185 492737
Hint
1.n的数据范围n100000
2.每个数的数据范围[-2e9,2e9]
解题报告
Splay的大模板题。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 100007;// 2e5 5;
int fa[MAX],cnt[MAX],tr[MAX][2],size[MAX],val[MAX],tot,root;
inline bool get(int x) {return tr[fa[x]][1]x;
}
inline void clear(int x) {fa[x]cnt[x]tr[x][0]tr[x][1]size[x]val[x]0;
}
inline void pushup(int x) {//更新x节点的信息 if(x 0) return;//其实不加也行因为不会去维护根节点的父节点的关系。size[x] cnt[x];
// if(tr[x][0]) size[x] size[tr[x][0]] ;
// if(tr[x][1]) size[x] size[tr[x][1]] ;没啥用、、size[x] size[tr[x][0]] size[tr[x][1]];
}
inline void rotate(int x) {//以下注释默认我是我爸的左儿子 int old fa[x],oldf fa[old],wget(x),wwget(old);//修改我爸和我右儿子的关系 tr[old][w] tr[x][w^1]; fa[tr[old][w]]old;//修改我和我爸的关系 tr[x][w^1] old;fa[old] x;//修改我和我爷爷的关系 fa[x] oldf;if(oldf) tr[oldf][ww] x;pushup(old);pushup(x);
} inline void splay(int x) {for(int oldfa[x]; old fa[x]; rotate(x)) {//默认根节点是0的情况下才可以这么用判断条件 if(fa[old]) {rotate(get(x) get(old) ? old : x);}}root x;
}
inline void insert(int x) {//x为权值 if(root 0) {val[tot] x;roottot;cnt[tot]size[tot]1;fa[tot] tr[tot][0]tr[tot][1]0;return; }int cur root,old 0;while(1) {if(x val[cur]) {cnt[cur];pushup(cur);pushup(old);splay(cur);return;}old cur;cur tr[cur][val[cur] x];if(cur 0) {val[tot] x;fa[tot] old; tr[tot][0]tr[tot][1]0; tr[old][xval[old]] tot;//维护父节点和孩子节点 cnt[tot] size[tot] 1;pushup(old); splay(tot);return;}}
}
inline int pre(int x) {int cur root,old0;while(cur) {if(val[cur] x) old cur,cur tr[cur][1];else cur tr[cur][0]; }return old;
}
inline int nxt(int x) {int cur root,old 0;while(cur) {if(val[cur] x) old cur,cur tr[cur][0];else cur tr[cur][1];}return old;
}
//inline int pre() {
// int cur tr[root][0];
// while(tr[cur][1]) cur tr[cur][1];
// return cur;
//}
//inline int nxt() {
// int cur tr[root][1];
// while(tr[cur][0]) cur tr[cur][0];
// return cur;
//}inline int Rank(int x) {//查询x的Rank int cur root,res 0;while(1) {
// if(cur 0) return -1;//说明数据非法 if(x val[cur]) cur tr[cur][0];else {res size[tr[cur][0]];if(x val[cur]) {splay(cur); return res1;}//此时x和树中的点重合树中不允许有两个相同的点res cnt[cur]; cur tr[cur][1];}}
}
inline int kth(int x) {//查询排名为x的数的val int cur root;while(1) {if(tr[cur][0] x size[tr[cur][0]]) cur tr[cur][0];else {int tmp size[tr[cur][0]] cnt[cur];if(x tmp) {splay(cur);return val[cur];}x - tmp;cur tr[cur][1];}}
}
inline void del(int x) {Rank(x);//找到x的排名并把它旋转上来if(cnt[root] 1) {cnt[root]--;return;}if(!tr[root][0] !tr[root][1]) root0;//可加个clear();函数else if(!tr[root][0]) {root tr[root][1];fa[root]0;} //pushup(root);else if(!tr[root][1]) {root tr[root][0];fa[root]0;}//pushup(root);else {int leftbig tr[root][0],oldrtroot;while(tr[leftbig][1]) leftbig tr[leftbig][1];splay(leftbig);tr[root][1]tr[oldrt][1];fa[tr[oldrt][1]]root;pushup(root);}
}
//全程表示根节点不是0但是根节点的父节点我们认为是0 (fa[rt]0)
int main()
{int n;cinn;for(int i 1; in; i) {int op,x;scanf(%d%d,op,x);if(op 1) insert(x);if(op 2) del(x);if(op 3) printf(%d\n,Rank(x));if(op 4) printf(%d\n,kth(x));if(op 5) printf(%d\n,val[pre(x)]);if(op 6) printf(%d\n,val[nxt(x)]);}return 0 ;
}
总结呜呜呜好难写、、、
