本文共 2563 字，大约阅读时间需要 8 分钟。
p.s.我只是拿来练treap的。。。treap比SBT真心好写啊。。。又参考了一下别人的treap写法。。真心飘逸。。。。学习之。。。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 using namespace std; 15 const int inf=~0u>>1; 16 const int mod = (int)1e6; 17 struct node{ 18 node *ch[2]; 19 int v,p,sz; 20 node(int _v,node *n): 21 v(_v){ch[0]=ch[1]=n;p=rand();sz=1;} 22 void upt(){sz=ch[0]->sz+ch[1]->sz+1;} 23 }; 24 struct Treap{ 25 node *root,*null; 26 Treap(){ 27 null=new node(0,0);null->sz=0;null->p=inf; 28 null->ch[0]=null->ch[1]=null; 29 root=null; 30 } 31 void rot(node *&t,bool d){ 32 node *_t=t->ch[d];t->ch[d]=_t->ch[!d]; 33 _t->ch[!d]=t;t->upt();_t->upt();t=_t; 34 } 35 void insert(node *&t,int val){ 36 if(t==null){t=new node(val,null);return;} 37 bool d=val > t->v; 38 insert(t->ch[d],val); 39 if(t->ch[d]->p < t->p)rot(t,d); 40 t->upt(); 41 } 42 void del(node *&t,int val){ 43 if(t==null)return; 44 if(val == t->v){ 45 bool d = t->ch[1]->p < t->ch[0]->p; 46 if(t->ch[d]==null){delete t;t=null;return;} 47 rot(t,d);del(t->ch[!d],val); 48 }else{ 49 bool d=val > t->v; 50 del(t->ch[d],val); 51 } 52 t->upt(); 53 } 54 node* pred(node *t,int val,node *ans){ 55 if(t==null)return ans; 56 if(t->v <= val) 57 return pred(t->ch[1],val,t); 58 else 59 return pred(t->ch[0],val,ans); 60 } 61 node *succ(node *t,int val,node *ans){ 62 if(t==null)return ans; 63 if(t->v >= val) 64 return succ(t->ch[0],val,t); 65 else 66 return succ(t->ch[1],val,ans); 67 } 68 int solve(int a){ 69 node *pre,*suc; 70 pre=pred(root,a,null); 71 suc=succ(root,a,null); 72 if(pre!=null&&suc!=null){ 73 if(abs(a-(pre->v))>abs(a-(suc->v))){ 74 del(root,suc->v); 75 return abs(a-(suc->v)); 76 }else{ 77 del(root,pre->v); 78 return abs(a-(pre->v)); 79 } 80 }else if(pre==null){ 81 del(root,suc->v); 82 return abs(a-(suc->v)); 83 }else if(suc==null){ 84 del(root,pre->v); 85 return abs(a-(pre->v)); 86 } 87 } 88 int size(){ 89 return root->sz; 90 } 91 }; 92 int main(){ 93 int n,op,a; 94 scanf("%d",&n); 95 Treap x,y; 96 int ans=0; 97 for(int i=1;i<=n;i++){ 98 scanf("%d%d",&op,&a); 99 if(op==0){100 if(y.size()==0){101 x.insert(x.root,a);102 }else{103 ans=(ans+y.solve(a))%mod;104 }105 }else if(op==1){106 if(x.size()==0){107 y.insert(y.root,a);108 }else{109 ans=(ans+x.solve(a))%mod;110 }111 }112 }113 printf("%d\n",ans%mod);114 return 0;115 }
转载于:https://www.cnblogs.com/silver-bullet/archive/2013/03/27/2985205.html