首页 > 代码库 > UESTC 395 Dynamic Query System --Treap
UESTC 395 Dynamic Query System --Treap
题意：让你维护一个集合，有8种操作：
1. I x 插入一个数
2. R x 删除x
3. S 输出总的数个数（集合大小）
4. L x 查询小于x的数的个数
5. W k 查询集合中数从小到大排列的第k个数
6. C x 查询x的个数
7. MI 查询集合中最小的数
8. MA 查询集合中最大的数
一道平衡树模拟的裸题，直接套版然后改下细节就行了。
代码：
#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>using namespace std;struct node{ node *ch[2]; int v,r,sz,cnt; void UP(){ sz = ch[0]->sz + ch[1]->sz + cnt; } int cmp(int x)const { if(x == v) return -1; return x > v; }}*null,*root;void create(node *&o,int v=0){ o = new node(); o->sz = o->cnt = 1; o->v = v; o->r = rand(); o->ch[0] = o->ch[1] = null;}void rotate(node *&o,int d){ node *p = o->ch[d]; o->ch[d] = p->ch[d^1]; p->ch[d^1] = o; o->UP(),p->UP(); o = p;}int countx(node *o,int v){ while(o != null) { int d = o->cmp(v); if(d == -1) return o->cnt; o = o->ch[d]; } return 0;}void insert(node *&o,int v){ if(o == null) { create(o,v); return; } int d = o->cmp(v); if(d == -1) { o->cnt++; o->UP(); return; } insert(o->ch[d],v); if(o->r > o->ch[d]->r) rotate(o,d); if(o != null) o->UP();}void del(node *&o,int v){ if(o == null) return; int d = o->cmp(v); if(d == -1) { if(o->cnt > 1) o->cnt--; else { if(o->ch[0] == null) o = o->ch[1]; else if(o->ch[1] == null) o = o->ch[0]; else { int d2 = o->ch[1]->r < o->ch[0]->r; if(o->ch[d2] == null) { delete o; o = null; return; } rotate(o,d2); del(o->ch[d2^1],v); } } } else del(o->ch[d],v); if(o != null) o->UP();}int Kth(node *o,int k){ if(o == null || k == 0 || k > o->sz) return -1; int left = o->ch[0]->sz; if(k > left && k <= left + o->cnt) return o->v; if(k > left + o->cnt) return Kth(o->ch[1],k-left-o->cnt); return Kth(o->ch[0],k);}int Count(node *o,int v){ if(o == null) return 0; int left = o->ch[0]->sz; if(o->v == v) return left; else if(v < o->v) return Count(o->ch[0],v); return Count(o->ch[1],v)+left+o->cnt;}void init(){ create(null); null->sz = 0; root = null;}int main(){ int t,n,i,x; char ss[3]; scanf("%d",&t); while(t--) { init(); scanf("%d",&n); while(n--) { scanf("%s",ss); if(ss[0] == ‘M‘) { if(ss[1] == ‘I‘) printf("%d\n",Kth(root,1)); else printf("%d\n",Kth(root,root->sz)); } else if(ss[0] == ‘I‘) { scanf("%d",&x); insert(root,x); } else if(ss[0] == ‘S‘) { printf("%d\n",root->sz); } else if(ss[0] == ‘R‘) { scanf("%d",&x); del(root,x); } else if(ss[0] == ‘L‘) { scanf("%d",&x); printf("%d\n",Count(root,x)); } else if(ss[0] == ‘W‘) { scanf("%d",&x); printf("%d\n",Kth(root,x)); } else if(ss[0] == ‘C‘) { scanf("%d",&x); printf("%d\n",countx(root,x)); } } } return 0;}
UESTC 395 Dynamic Query System --Treap
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。