郑州模板建站哪家好,wordpress上传附件失败,html5网站开发特点,深圳公司建设网站制作您需要写一种数据结构#xff08;可参考题目标题#xff09;#xff0c;来维护一些数#xff0c;其中需要提供以下操作#xff1a;
插入数值x。删除数值x(若有多个相同的数#xff0c;应只删除一个)。查询数值x的排名(若有多个相同的数#xff0c;应输出最小的排名)。查…您需要写一种数据结构可参考题目标题来维护一些数其中需要提供以下操作
插入数值x。删除数值x(若有多个相同的数应只删除一个)。查询数值x的排名(若有多个相同的数应输出最小的排名)。查询排名为x的数值。求数值x的前驱(前驱定义为小于x的最大的数)。求数值x的后继(后继定义为大于x的最小的数)。 注意 数据保证查询的结果一定存在。 本题为平衡树基本操作的代码实现
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 100010, INF 1e8;int n;
struct Node
{int l, r;int key, val;int cnt, size;
}tr[N];int 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].cnt tr[idx].size 1;return idx;
}void zig(int p) // 右旋
{int q tr[p].l;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;tr[p].r tr[q].l, tr[q].l p, p q;pushup(tr[p].l), pushup(p);
}void build()
{get_node(-INF), get_node(INF);root 1, tr[1].r 2;pushup(root);if (tr[1].val tr[2].val) zag(root);
}void insert(int p, int key)
{if (!p) p get_node(key);else if (tr[p].key key) tr[p].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)
{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;}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;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()
{build();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);else if (opt 4) printf(%d\n, get_key_by_rank(root, x 1));else if (opt 5) printf(%d\n, get_prev(root, x));else printf(%d\n, get_next(root, x));}return 0;
}Vector版偷懒平衡树
#includecstdio
#includevector
#includealgorithm
using namespace std;
vectorintv;
int n,opt,x;
int main()
{v.reserve(100001);scanf(%d,n);while(n--){scanf(%d%d,opt,x);if(opt1) v.insert(lower_bound(v.begin(),v.end(),x),x);if(opt2) v.erase (lower_bound(v.begin(),v.end(),x));if(opt3) printf(%d\n,lower_bound(v.begin(),v.end(),x)-v.begin()1);if(opt4) printf(%d\n,v[x-1]);if(opt5) printf(%d\n,v[lower_bound(v.begin(),v.end(),x)-v.begin()-1]);if(opt6) printf(%d\n,v[upper_bound(v.begin(),v.end(),x)-v.begin()]);}return 0;
}
