首页 > 代码库 > SPOJ 3273 - Order statistic set , Treap
SPOJ 3273 - Order statistic set , Treap
点击打开链接
题意:
集合S支持一下四种操作:
INSERT(S,x) : 如果S中没有x,则插入x
DELETE(S,x): 如果S中有x,则删除x
K-TH(S): 输出S中第K小的数
COUNT(S,x): 统计S中小于x的数有多少个
一共有Q(1 ≤ Q ≤ 200000)次操作。
Treap模板。。
#include<cstdio> #include<cstring> #include<cstdlib> const int inf=0x3f3f3f3f; struct Node { Node *ch[2]; int r, v, s; Node(int v):v(v) { ch[0] = ch[1] = NULL; r = rand(); s = 1; } int cmp(int x) const { if (x == v) return -1; return (x < v) ? 0 : 1; } void maintain() { s = 1; if(ch[0] != NULL) s += ch[0]->s; if(ch[1] != NULL) s += ch[1]->s; } }; void rotate(Node* &o, int d) { Node* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o; o->maintain(); k->maintain(); o = k; } void insert(Node* &o, int x) { if(o == NULL) o = new Node(x); else{ /*int d = (x < o->v ? 0 : 1); // 允许插入相同结点*/ int d =o->cmp(x); if(d==-1) return ; //不允许插入相同结点*/ insert(o->ch[d], x); if(o->ch[d]->r > o->r) rotate(o, d^1); else o->maintain(); } } void remove(Node* &o, int x) { int d = o->cmp(x); if(d == -1) { Node* u = o; if(o->ch[0] != NULL && o->ch[1] != NULL) { int d2 = (o->ch[0]->r > o->ch[1]->r) ? 1 : 0; rotate(o, d2); remove(o->ch[d2], x); }else{ if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0]; delete u; } }else remove(o->ch[d], x); if(o != NULL) o->maintain(); } int find(Node* o, int x){ while(o != NULL){ int d = o->cmp(x); if(d == -1) return 1; o = o->ch[d]; } return 0; } int kth(Node* o,int k){///kth small while(o != NULL){ int s = (o->ch[0] == NULL) ? 0 : o->ch[0]->s; if(k==s+1) return o->v; else if(k<=s) o=o->ch[0]; else{ o=o->ch[1]; k=k-s-1; } } return -inf; } int rank(Node* o, int x){ int ret = 0; while(o != NULL){ int s = (o->ch[0] == NULL) ? 0 : o->ch[0]->s; if(o->v < x){ <span style="color:#ff0000;">//由于是统计比x小的数的个数,所以不能取等号</span> ret += s + 1; o = o->ch[1]; }else{ o = o->ch[0]; } } return ret; } int main() { int q; Node* root=NULL; //freopen("in.txt","r",stdin); scanf("%d",&q); while(q--) { char cmd[3];int nb; scanf("%s%d",cmd,&nb); if(cmd[0]=='I'&&find(root,nb)==0) { insert(root,nb); } else if(cmd[0]=='D'&&find(root,nb)==1) { remove(root,nb); } else if(cmd[0]=='K') { int temp=kth(root,nb); if(temp == -inf) puts("invalid"); else printf("%d\n",temp); } else if(cmd[0]=='C') { printf("%d\n",rank(root,nb)); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。