咸阳市城乡建设规划局网站,网站网页链接,大型网站建设公司有哪些,郑州陆港开发建设有限公司网站题目大意#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且最小的数) 思路 直接splay 今天才敲。。。 1 #includeiostream2 #includecstdio3 #includecmath4 #includecstdlib5 #includecstring6 #includealgorithm7 #includevector8 #includequeue9 #define inf 213906214310 #define ll long long11 #define MAXN 100100 12 #define MOD 100000000713 using namespace std;14 inline int read()15 {16 int x0,f1;char chgetchar();17 while(!isdigit(ch)) {if(ch-) f-1;chgetchar();}18 while(isdigit(ch)) {xx*10ch-0;chgetchar();}19 return x*f;20 }21 int ch[MAXN][2],fa[MAXN],sz,cnt[MAXN],val[MAXN],size[MAXN],rt;22 int which(int x) {return xch[fa[x]][1];}23 int find_pre()24 {25 int posch[rt][0];26 while(ch[pos][1]) posch[pos][1];27 return pos;28 }29 int find_sub()30 {31 int posch[rt][1];32 while(ch[pos][0]) posch[pos][0];33 return pos;34 }35 void upd(int x)36 {37 if(!x) return ;38 size[x]cnt[x]size[ch[x][1]]size[ch[x][0]];39 }40 void rotate(int pos)41 {42 int ffa[pos],fffa[f],kwhich(pos);43 ch[f][k]ch[pos][k^1],fa[ch[f][k]]f,fa[f]pos,ch[pos][k^1]f,fa[pos]ff;44 if(ff) ch[ff][ch[ff][1]f]pos;45 upd(f);upd(pos);46 }47 void splay(int x)48 {49 for(int f;ffa[x];rotate(x))50 if(fa[f]) rotate((which(x)which(f)?f:x));51 rtx;52 }53 void Insert(int x)54 {55 int posrt,f0;56 while(1)57 {58 if(val[pos]x) {cnt[pos],upd(pos);upd(f);splay(pos);return ;}59 fpos,posch[pos][xval[pos]];60 if(!pos)61 {62 ch[sz][0]ch[sz][1]0,fa[sz]f,val[sz]x,cnt[sz]size[sz]1,ch[f][xval[f]]sz;63 upd(f);splay(sz);return ;64 }65 }66 }67 void insert(int x)68 {69 if(!rt) {val[sz]x,ch[sz][0]ch[sz][1]fa[sz]0,cnt[sz]size[sz]1,rtsz;return;}70 Insert(x);71 }72 int find_rank(int x)73 {74 int res0,posrt;75 while(1)76 {77 if(xval[pos]) posch[pos][0];78 else79 {80 ressize[ch[pos][0]];81 if(val[pos]x) {splay(pos);return res1;}82 rescnt[pos],posch[pos][1];83 }84 }85 }86 int find_num(int x)87 {88 int tmp0,posrt;89 while(1)90 {91 if(ch[pos][0]xsize[ch[pos][0]]) posch[pos][0];92 else93 {94 tmpsize[ch[pos][0]]cnt[pos];95 if(xtmp) return val[pos];96 x-tmp,posch[pos][1];97 }98 }99 }
100 void dlt(int x)
101 {
102 find_rank(x);
103 if(cnt[rt]1) {cnt[rt]--;return ;}
104 if(!ch[rt][0]!ch[rt][1]) {rt0;return ;}
105 if(!ch[rt][0]||!ch[rt][1])
106 {
107 int k!ch[rt][1]?0:1;
108 rtch[rt][k],fa[rt]0;
109 return ;
110 }
111 int kfind_pre(),tmprt;
112 splay(k);fa[ch[tmp][1]]rt;
113 ch[rt][1]ch[tmp][1],rtk;
114 }
115 int main()
116 {
117 int Tread(),opt,x;
118 while(T--)
119 {
120 optread(),xread();
121 if(opt1) insert(x);
122 if(opt2) dlt(x);
123 if(opt3) printf(%d\n,find_rank(x));
124 if(opt4) printf(%d\n,find_num(x));
125 if(opt5) {insert(x);printf(%d\n,val[find_pre()]);dlt(x);}
126 if(opt6) {insert(x);printf(%d\n,val[find_sub()]);dlt(x);}
127 }
128 } View Code 转载于:https://www.cnblogs.com/yyc-jack-0920/p/8047274.html
