网站服务内容有哪些,WordPress搜索插件主题,广告牌样式图片大全,就业网站建设正题
评测记录:https://www.luogu.org/recordnew/lists?uidSSL_WYC_zombieeeeeepidP3369statussort0 题目大意
要求支持查询一个数字的排名#xff0c;查询该排名的数字#xff0c;插入数字#xff0c;删除数字#xff0c;求前驱后继。 解题思路
有旋Tr…正题
评测记录:https://www.luogu.org/recordnew/lists?uidSSL_WYC_zombieeeeeepidP3369statussort0 题目大意
要求支持查询一个数字的排名查询该排名的数字插入数字删除数字求前驱后继。 解题思路
有旋Treap不解释。 codecodecode
#includecstdio
#includealgorithm
#define INF 2147483647/3
#define N 100010
using namespace std;
int n,root;
struct Treap_node{int l[N],r[N];int val[N],dat[N];int cnt[N],size[N];int tot;int New(int new_val){val[tot]new_val;dat[tot]rand();cnt[tot]size[tot]1;return tot;}void Updata(int p){size[p]size[l[p]]size[r[p]]cnt[p];}void Build(){New(-INF);New(INF);root1;r[1]2;Updata(root);}int GetRankByVal(int p,int num){if(p0) return 0;if(numval[p]) return size[l[p]]1;if(numval[p]) return GetRankByVal(l[p],num);return GetRankByVal(r[p],num)size[l[p]]cnt[p];}int GetValByRank(int p,int rank){if (p0) return INF;if(size[l[p]]rank) return GetValByRank(l[p],rank);if(size[l[p]]cnt[p]rank) return val[p];return GetValByRank(r[p],rank-size[l[p]]-cnt[p]);}void zig(int p){int ql[p];l[p]r[q];r[q]p;pq;Updata(r[p]);Updata(p);}void zag(int p){int qr[p];r[p]l[q];l[q]p;pq;Updata(l[p]);Updata(p);}void Insert(int p,int num){if(p0){pNew(num);return;}if(numval[p]){cnt[p];Updata(p);return;}if(numval[p]){Insert(l[p],num);if(dat[p]dat[l[p]]) zig(p);}else{Insert(r[p],num);if(dat[p]dat[r[p]]) zag(p);}Updata(p);}int GetPre(int num){int ans1;int proot;while(p){if(numval[p]){if(l[p]0){pl[p];while(r[p]0) pr[p];ansp;}break;}if(val[p]numval[p]val[ans]) ansp;pnumval[p]?l[p]:r[p];}return val[ans];}int GetNext(int num){int ans2;int proot;while(p){if(numval[p]){if(r[p]0){pr[p];while(l[p]0) pl[p];ansp;}break;}if(val[p]numval[p]val[ans]) ansp;pnumval[p]?l[p]:r[p];}return val[ans];}void Remove(int p,int num){if(p0) return;if(numval[p]){if(cnt[p]1){cnt[p]--;Updata(p);return;}if(l[p]||r[p]){if(r[p]0||dat[l[p]]dat[r[p]])zig(p),Remove(r[p],num);elsezag(p),Remove(l[p],num);Updata(p);}else p0;return;}numval[p]?Remove(l[p],num):Remove(r[p],num);Updata(p);}
}a;
int main()
{a.Build();scanf(%d,n);while(n--){int opt,x;scanf(%d%d,opt,x);switch(opt){case 1:a.Insert(root,x);break;case 2:a.Remove(root,x);break;case 3:printf(%d\n,a.GetRankByVal(root,x)-1);break;case 4:printf(%d\n,a.GetValByRank(root,x1));break;case 5:printf(%d\n,a.GetPre(x));break;case 6:printf(%d\n,a.GetNext(x));break;}}
}
