SBT 专辑

先上模板，应该每个人都写得差不多的：

基本上包含了sbt的所有基本操作。

View Code

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <iostream>
  5 #include <algorithm>
  6 
  7 #define N 100010 
  8 
  9 using namespace std;
 10 
 11 int key[N],lt[N],rt[N],sz[N];
 12 int root,cnt;
 13 
 14 void rotate_l(int &x)//left rotate
 15 {
 16     int y=rt[x];
 17     rt[x]=lt[y];
 18     lt[y]=x;
 19     sz[y]=sz[x];
 20     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 21     x=y;
 22 }
 23 
 24 void rotate_r(int &x)//right rotate
 25 {
 26     int y=lt[x];
 27     lt[x]=rt[y];
 28     rt[y]=x;
 29     sz[y]=sz[x];
 30     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 31     x=y;
 32 }
 33 
 34 void maintain(int &x,bool fg)
 35 {
 36     if(!fg)
 37     {
 38         if(sz[lt[lt[x]]]>sz[rt[x]]) rotate_r(x);
 39         else if(sz[rt[lt[x]]]>sz[rt[x]]) rotate_l(lt[x]),rotate_r(x);
 40         else return;
 41     }
 42     else
 43     {
 44         if(sz[rt[rt[x]]]>sz[lt[x]]) rotate_l(x);
 45         else if(sz[lt[rt[x]]]>sz[lt[x]]) rotate_r(rt[x]),rotate_l(x);
 46         else return;
 47     }
 48     maintain(lt[x],false);
 49     maintain(rt[x],true);
 50     maintain(x,true);
 51     maintain(x,false);
 52 }
 53 
 54 void insert(int &x,int sp)
 55 {
 56     if(!x)
 57     {
 58         x=++cnt;
 59         lt[x]=rt[x]=0;
 60         sz[x]=1;
 61         key[x]=sp;
 62     }
 63     else
 64     {
 65         sz[x]++;
 66         if(sp<key[x]) insert(lt[x],sp);
 67         else insert(rt[x],sp);
 68         maintain(x,sp>=key[x]);
 69     }
 70 }
 71 
 72 int del(int &x,int sp)
 73 {
 74     sz[x]--;
 75     if(sp==key[x]||(sp<key[x]&&lt[x]==0)||(sp>key[x]&&rt[x]==0))
 76     {
 77         int y=key[x];
 78         if(lt[x]==0||rt[x]==0) x=lt[x]+rt[x];
 79         else key[x]=del(lt[x],key[x]+1);
 80         return y;
 81     }
 82     else
 83     {
 84         if(sp<key[x]) return del(lt[x],sp);
 85         else return del(rt[x],sp);
 86     }
 87 }
 88 
 89 int getmin()
 90 {
 91     int i;
 92     for(i=root;lt[i];i=lt[i]);
 93     return key[i];
 94 }
 95 
 96 int getmax()
 97 {
 98     int i;
 99     for(i=root;rt[i];i=rt[i]);
100     return key[i];
101 }
102 
103 int select(int &x,int rak)
104 {
105     int rk=sz[lt[x]]+1;
106     if(rk==rak) return key[x];
107     else if(rk<rak) return select(rt[x],rak-rk);
108     return select(lt[x],rak);
109 }
110 
111 int rank(int &x,int sp)
112 {
113     if(sp<key[x]) return rank(lt[x],sp);
114     else if(sp>key[x]) return rank(rt[x],sp)+sz[lt[x]]+1;
115     return sz[lt[x]]+1;
116 }
117 
118 int pred(int &x,int y,int sp)
119 {
120     if(x==0) return y;
121     if(key[x]<sp) return pred(rt[x],x,sp);
122     return pred(lt[x],y,sp);
123 }
124 
125 int succ(int &x,int y,int sp)
126 {
127     if(x==0) return y;
128     if(key[x]>sp) return succ(lt[x],x,sp);
129     return succ(rt[x],y,sp);
130 }
131 
132 void go()
133 {
134     root=cnt=0;
135     int x;
136     char ch;
137     while(scanf("%c %d",&ch,&x)!=EOF)
138     {
139         if(ch=='I') insert(root,x);
140         else if(ch=='D') printf("%d\n",del(root,x));
141         else if(ch=='K') printf("%d\n",select(root,x));
142         else if(ch=='R') printf("%d\n",rank(root,x));
143         else if(ch=='P') printf("%d\n",key[pred(root,0,x)]);
144         else if(ch=='S') printf("%d\n",key[succ(root,0,x)]);
145     }
146 }
147 
148 int main()
149 {
150     go();
151     return 0;
152 }

相关题目：

ps:模板不是用来水题的，只是方便复习。

不粘模板手敲一遍没坏处~

BZOJ 1058：

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cstdlib>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 inline void rotate_l(int &x)
10 {
11     int y=rt[x];
12     rt[x]=lt[y];
13     lt[y]=x;
14     sz[y]=sz[x];
15     sz[x]=sz[lt[x]]sz[rt[x]]+1;
16     x=y;
17 }
18 
19 inline void rotate_r(int &x)
20 {
21     int y=lt[x];
22     lt[x]=rt[y];
23     rt[y]=x;
24     sz[y]=sz[x];
25     sz[x]=sz[lt[x]]+sz[rt[]x]+1;
26     x=y;
27 }
28 
29 inline void maintain(int &x,int fg)
30 {
31     if(!fg)
32     {
33         if(sz[lt[lt[x]]]>sz[rt[x]]) rotate_r(x);
34         else if(sz[rt[lt[x]]]>sz[rt[x]]) rotate_l(lt[x]),rotate_r(x);
35         else return;
36     }
37     else
38     {
39         if(sz[rt[rt[x]]]>sz[lt[x]]) rotate_l(x);
40         else if(sz[lt[rt[x]]]>sz[lt[x]]) rotate_r(rt[x]),rotate_l(x);
41         else return;
42     }
43     maintain(lt[x],0);
44     maintain(rt[x],1);
45     maintain(x,1);
46     maintain(x,,0);
47 }
48 
49 inline void insert(int &x,int po,int va)
50 {
51     if(!x)
52     {
53         x=++cnt;
54         lt[x]=rt[x]=0;
55         sz[x]=1; key[x]=va;
56     }
57     else
58     {
59         sz[x]++;
60         if(po<sz[lt[x]]) insert(lt[x],po,va);
61         else insert(rt[x],po-sz[lt[x]]);
62         maintain(x,po>=sz[lt[x]]);
63     }
64 }
65 
66 inline void go()
67 {
68     root=cnt=0;
69     scanf("%d%d",n,&m);
70     for(int i=1;i<=n;i++)
71     {
72         scanf("%d",&a);
73         insert(root,i-1,a);
74     }
75 }
76 
77 int main()
78 {
79     go();
80     return 0;
81 }

BZOJ 1208:

View Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <cstdlib>
  6 #include <cmath>
  7 
  8 #define N 1000000
  9 #define INF 1e9    //一定要够大啊！1e8跪了！ 
 10 #define mod 1000000
 11 
 12 using namespace std;
 13 
 14 int sz[N],lt[N],rt[N],val[N];
 15 int n,cnt,root,people,ans;
 16 
 17 inline void rotate_l(int &x)
 18 {
 19     int y=rt[x];
 20     rt[x]=lt[y];
 21     lt[y]=x;
 22     sz[y]=sz[x];
 23     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 24     x=y;
 25 }
 26 
 27 inline void rotate_r(int &x)
 28 {
 29     int y=lt[x];
 30     lt[x]=rt[y];
 31     rt[y]=x;
 32     sz[y]=sz[x];
 33     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 34     x=y;
 35 }
 36 
 37 inline void maintain(int &x,int fg)
 38 {
 39     if(!fg)
 40     {
 41         if(sz[lt[lt[x]]]>sz[rt[x]]) rotate_r(x);
 42         else if(sz[rt[lt[x]]]>sz[rt[x]]) rotate_l(lt[x]),rotate_r(x);
 43         else return;
 44     }
 45     else
 46     {
 47         if(sz[rt[rt[x]]]>sz[lt[x]]) rotate_l(x);
 48         else if(sz[lt[rt[x]]]>sz[lt[x]]) rotate_r(rt[x]),rotate_l(x);
 49         else return;
 50     }
 51     maintain(lt[x],0); maintain(rt[x],1);
 52     maintain(x,1); maintain(x,0);
 53 }
 54 
 55 inline void insert(int &x,int sp)
 56 {
 57     if(!x)
 58     {
 59         x=++cnt;
 60         lt[x]=rt[x]=0;
 61         sz[x]=1; val[x]=sp;
 62     }
 63     else
 64     {
 65         sz[x]++;
 66         if(sp<val[x]) insert(lt[x],sp);
 67         else insert(rt[x],sp);
 68         maintain(x,sp>=val[x]);
 69     }
 70 } 
 71 
 72 inline int pred(int &x,int y,int sp)
 73 {
 74     if(!x) return y;
 75     else if(sp>val[x]) return pred(rt[x],x,sp);
 76     return pred(lt[x],y,sp);
 77 }
 78 
 79 inline int succ(int &x,int y,int sp)
 80 {
 81     if(!x) return y;
 82     else if(sp<val[x]) return succ(lt[x],x,sp);
 83     return succ(rt[x],y,sp);
 84 }
 85 
 86 int del(int &x,int sp)
 87 {
 88     sz[x]--;
 89     if(sp==val[x]||(sp<val[x]&&lt[x]==0)||(sp>val[x]&&rt[x]==0))
 90     {
 91         int y=val[x];
 92         if(lt[x]==0||rt[x]==0) x=lt[x]+rt[x];
 93         else val[x]=del(lt[x],val[x]+1);
 94         return y;
 95     }
 96     else
 97     {
 98         if(sp<val[x]) return del(lt[x],sp);
 99         else return del(rt[x],sp);
100     }
101 }
102 
103 inline void go()
104 {
105     root=cnt=0;
106     scanf("%d",&n);
107     for(int i=1,f1,f2,pd,da;i<=n;i++)
108     {
109         scanf("%d%d",&pd,&da);
110         if(sz[root]==0||pd==people)
111         {
112             people=pd;
113             insert(root,da);
114             continue;
115         }
116         f1=pred(root,0,da);
117         f2=succ(root,0,da);
118         if(f1!=0) f1=val[f1];
119         else f1=INF;
120         if(f2!=0) f2=val[f2];
121         else f2=INF;
122         if(abs(f1-da)<=abs(f2-da)) del(root,f1),ans+=abs(f1-da)%mod;
123         else del(root,f2),ans+=abs(f2-da)%mod;
124         ans%=mod;
125     }
126     printf("%d\n",ans);
127 }
128 
129 int main()
130 {
131     go();
132     return 0;
133 }

BZOJ 1503:

View Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 
  7 #define N 1000000
  8 
  9 using namespace std;
 10 
 11 int val[N],rt[N],lt[N],sz[N];
 12 int n,m,cnt,co,root;
 13 
 14 inline void rotate_l(int &x)
 15 {
 16     int y=rt[x];
 17     rt[x]=lt[y];
 18     lt[y]=x;
 19     sz[y]=sz[x];
 20     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 21     x=y;
 22 }
 23 
 24 inline void rotate_r(int &x)
 25 {
 26     int y=lt[x];
 27     lt[x]=rt[y];
 28     rt[y]=x;
 29     sz[y]=sz[x];
 30     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 31     x=y;
 32 }
 33 
 34 inline void maintain(int &x,int fg)
 35 {
 36     if(!fg)
 37     {
 38         if(sz[lt[lt[x]]]>sz[rt[x]]) rotate_r(x);
 39         else if(sz[rt[lt[x]]]>sz[rt[x]]) rotate_l(lt[x]),rotate_r(x);
 40         else return;
 41     }
 42     else
 43     {
 44         if(sz[rt[rt[x]]]>sz[lt[x]]) rotate_l(x);
 45         else if(sz[lt[rt[x]]]>sz[lt[x]]) rotate_r(rt[x]),rotate_l(x);
 46         else return;
 47     }
 48     maintain(lt[x],0); maintain(rt[x],1);
 49     maintain(x,1); maintain(x,0);
 50 }
 51 
 52 inline void insert(int &x,int sp)
 53 {
 54     if(!x)
 55     {
 56         x=++cnt;
 57         lt[x]=rt[x]=0;
 58         sz[x]=1; val[x]=sp;
 59     }
 60     else
 61     {
 62         sz[x]++;
 63         if(sp<val[x]) insert(lt[x],sp);
 64         else insert(rt[x],sp);
 65         maintain(x,sp>=val[x]);
 66     }
 67 }
 68 
 69 inline int select(int &x,int rak)
 70 {
 71     int rk=sz[lt[x]]+1;
 72     if(rak==rk) return val[x];
 73     else if(rak<rk) return select(lt[x],rak);
 74     return select(rt[x],rak-rk);
 75 }
 76 
 77 inline void del(int &x)//SBT的区间删除 
 78 {
 79     if(!x) return;
 80     if(val[x]+co<m) x=rt[x],del(x);//注意细节 
 81     else del(lt[x]),sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 82 }
 83 
 84 inline void go()
 85 {
 86     root=cnt=co=0;
 87     scanf("%d%d",&n,&m);
 88     char str[10];int da;
 89     for(int i=1;i<=n;i++)
 90     {
 91         scanf("%s%d",str,&da);
 92         if(str[0]=='I')
 93         {
 94             if(da<m) continue;
 95             insert(root,da-co);
 96         }
 97         else if(str[0]=='A') co+=da;
 98         else if(str[0]=='S') co-=da,del(root);
 99         else
100         {
101             if(da>sz[root]) puts("-1");
102             else printf("%d\n",select(root,sz[root]-da+1)+co);
103         }
104     }
105     printf("%d\n",cnt-sz[root]);
106 }
107 
108 int main()
109 {
110     go();
111     return 0;
112 }

BZOJ 1588:

View Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 #include <cmath>
  7 
  8 #define N 1000000
  9 #define INF 1e9
 10 #define ZERO 1000000
 11 
 12 using namespace std;
 13 
 14 int sz[N],lt[N],rt[N],val[N];
 15 int root,n,cnt,ans;
 16 bool vis[2000000];
 17 
 18 inline void rotate_l(int &x)
 19 {
 20     int y=rt[x];
 21     rt[x]=lt[y];
 22     lt[y]=x;
 23     sz[y]=sz[x];
 24     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 25     x=y;
 26 }
 27 
 28 inline void rotate_r(int &x)
 29 {
 30     int y=lt[x];
 31     lt[x]=rt[y];
 32     rt[y]=x;
 33     sz[y]=sz[x];
 34     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 35     x=y;
 36 }
 37 
 38 inline void maintain(int &x,int fg)
 39 {
 40     if(!fg)
 41     {
 42         if(sz[lt[lt[x]]]>sz[rt[x]]) rotate_r(x);
 43         else if(sz[rt[lt[x]]]>sz[rt[x]]) rotate_l(lt[x]),rotate_r(x);
 44         else return;
 45     }
 46     else
 47     {
 48         if(sz[rt[rt[x]]]>sz[lt[x]]) rotate_l(x);
 49         else if(sz[lt[rt[x]]]>sz[lt[x]]) rotate_r(rt[x]),rotate_l(x);
 50         else return;
 51     }
 52     maintain(lt[x],0); maintain(rt[x],1);
 53     maintain(x,1); maintain(x,0);
 54 }
 55 
 56 inline void insert(int &x,int sp)
 57 {
 58     if(!x)
 59     {
 60         x=++cnt; lt[x]=rt[x]=0;
 61         sz[x]=1; val[x]=sp;
 62     }
 63     else
 64     {
 65         sz[x]++;
 66         if(sp<val[x]) insert(lt[x],sp);
 67         else insert(rt[x],sp);
 68         maintain(x,sp>=val[x]);
 69     }
 70 }
 71 
 72 inline int pred(int &x,int y,int sp)
 73 {
 74     if(!x) return y;
 75     else if(sp>val[x]) return pred(rt[x],x,sp);
 76     return pred(lt[x],y,sp);
 77 }
 78 
 79 inline int succ(int &x,int y,int sp)
 80 {
 81     if(!x) return y;
 82     else if(sp<val[x]) return succ(lt[x],x,sp);
 83     return succ(rt[x],y,sp);
 84 }
 85 
 86 inline void go()
 87 {
 88     root=cnt=0;
 89     scanf("%d%d",&n,&ans); insert(root,ans); vis[ZERO+ans]=true;
 90     for(int i=2,a,f1,f2;i<=n;i++)
 91     {
 92         if(scanf("%d",&a)==EOF) a=0;
 93         if(vis[ZERO+a]) continue;
 94         vis[ZERO+a]=true;
 95         f1=pred(root,0,a);
 96         if(f1!=0) f1=val[f1];
 97         else f1=-INF;
 98         f2=succ(root,0,a);
 99         if(f2!=0) f2=val[f2];
100         else f2=-INF;
101         ans+=min(abs(f1-a),abs(f2-a));
102         insert(root,a);
103     }
104     printf("%d\n",ans);
105 }
106 
107 int main()
108 {
109     go();
110     return 0;
111 }

POJ 2761:

View Code

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 
  7 #define N 150000
  8 
  9 using namespace std;
 10 
 11 int lt[N],rt[N],sz[N],key[N];
 12 int n,m,cnt,root,sa[N];
 13 
 14 struct PX
 15 {
 16     int l,r,k,ans,id;
 17 }px[N];
 18 
 19 inline bool cmp(const PX &a,const PX &b)
 20 {
 21     if(a.l==b.l) return a.r<b.r;
 22     return a.l<b.l;
 23 }
 24 
 25 inline bool cmp1(const PX &a,const PX &b)
 26 {
 27     return a.id<b.id;
 28 }
 29 
 30 void read()
 31 {
 32     memset(lt,0,sizeof lt);
 33     memset(rt,0,sizeof rt);
 34     memset(sz,0,sizeof sz);
 35     memset(key,0,sizeof key);
 36     for(int i=1;i<=n;i++) scanf("%d",&sa[i]);
 37     for(int i=1;i<=m;i++)
 38     {
 39         scanf("%d%d%d",&px[i].l,&px[i].r,&px[i].k);
 40         px[i].id=i;
 41     }
 42     sort(px+1,px+1+m,cmp);
 43 }
 44 
 45 void rotate_l(int &x)//left rotate
 46 {
 47     int y=rt[x];
 48     rt[x]=lt[y];
 49     lt[y]=x;
 50     sz[y]=sz[x];
 51     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 52     x=y;
 53 }
 54 
 55 void rotate_r(int &x)//right rotate
 56 {
 57     int y=lt[x];
 58     lt[x]=rt[y];
 59     rt[y]=x;
 60     sz[y]=sz[x];
 61     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 62     x=y;
 63 }
 64 
 65 int select(int &x,int rak)
 66 {
 67     int rk=sz[lt[x]]+1;
 68     if(rk==rak) return key[x];
 69     else if(rk<rak) return select(rt[x],rak-rk);
 70     else return select(lt[x],rak);
 71 }
 72 
 73 int del(int &x,int sp)
 74 {
 75     sz[x]--;
 76     if(sp==key[x]||(sp<key[x]&&lt[x]==0)||(sp>key[x]&&rt[x]==0))
 77     {
 78         int y=key[x];
 79         if(lt[x]==0||rt[x]==0) x=lt[x]+rt[x];
 80         else key[x]=del(lt[x],key[x]+1);
 81         return y;
 82     }
 83     else
 84     {
 85         if(sp<key[x]) return del(lt[x],sp);
 86         else return del(rt[x],sp);
 87     }
 88 }
 89 
 90 void maintain(int &x,bool fg)
 91 {
 92     if(!fg)
 93     {
 94         if(sz[lt[lt[x]]]>sz[rt[x]]) rotate_r(x);
 95         else if(sz[rt[lt[x]]]>sz[rt[x]]) rotate_l(lt[x]),rotate_r(x);
 96         else return;
 97     }
 98     else
 99     {
100         if(sz[rt[rt[x]]]>sz[lt[x]]) rotate_l(x);
101         else if(sz[lt[rt[x]]]>sz[lt[x]]) rotate_r(rt[x]),rotate_l(x);
102         else return;
103     }
104     maintain(rt[x],true);
105     maintain(lt[x],false);
106     maintain(x,false);
107     maintain(x,true);
108 }
109 
110 void insert(int &x,int sp)
111 {
112     if(!x)
113     {
114         x=++cnt;
115         lt[x]=rt[x]=0;
116         sz[x]=1;
117         key[x]=sp;
118     }
119     else
120     {
121         sz[x]++;
122         if(sp<key[x]) insert(lt[x],sp);
123         else insert(rt[x],sp);
124         maintain(x,sp>=key[x]);
125     }
126 }
127 
128 void sout(int l,int r)
129 {
130     for(int i=l;i<=r;i++) del(root,sa[i]);
131 }
132 
133 void sin(int l,int r)
134 {
135     for(int i=l;i<=r;i++) insert(root,sa[i]);
136 }
137 
138 void go()
139 {
140     root=cnt=0;
141     sin(px[1].l,px[1].r);
142     px[1].ans=select(root,px[1].k);
143     for(int i=2;i<=m;i++)
144     {
145         if(px[i-1].r<px[i].l)
146         {
147             sout(px[i-1].l,px[i-1].r);
148             sin(px[i].l,px[i].r);
149         }
150         else
151         {
152             sout(px[i-1].l,px[i].l-1);
153             sin(px[i-1].r+1,px[i].r);
154         }
155         px[i].ans=select(root,px[i].k);
156     }
157     sort(px+1,px+1+m,cmp1);
158     for(int i=1;i<=m;i++) printf("%d\n",px[i].ans);
159 }
160 
161 int main()
162 {
163     while(scanf("%d%d",&n,&m)!=EOF)
164     {
165         read();
166         go();    
167     }
168     return 0;
169 }

POJ 2892:

View Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <cstdlib>
  6 
  7 #define N 100000
  8 
  9 using namespace std;
 10 
 11 int lt[N],rt[N],sz[N],val[N];
 12 int q[N];
 13 int n,m,root,cnt,h;
 14 bool vis[N];
 15 
 16 inline void rotate_r(int &x)
 17 {
 18     int y=lt[x];
 19     lt[x]=rt[y];
 20     rt[y]=x;
 21     sz[y]=sz[x];
 22     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 23     x=y;
 24 }
 25 
 26 inline void rotate_l(int &x)
 27 {
 28     int y=rt[x];
 29     rt[x]=lt[y];
 30     lt[y]=x;
 31     sz[y]=sz[x];
 32     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 33     x=y;
 34 }
 35 
 36 inline void maintain(int &x,int fg)
 37 {
 38     if(!fg)
 39     {
 40         if(sz[lt[lt[x]]]>sz[rt[x]]) rotate_r(x);
 41         else if(sz[rt[lt[x]]]>sz[rt[x]]) rotate_l(lt[x]),rotate_r(x);
 42         else return;
 43     }
 44     else
 45     {
 46         if(sz[rt[rt[x]]]>sz[lt[x]]) rotate_l(x);
 47         else if(sz[lt[rt[x]]]>sz[lt[x]]) rotate_r(rt[x]),rotate_l(x);
 48         else return;
 49     }
 50     maintain(lt[x],0); maintain(rt[x],1);
 51     maintain(x,1); maintain(x,0);
 52 }
 53 
 54 inline void insert(int &x,int sp)
 55 {
 56     if(!x)
 57     {
 58         x=++cnt;
 59         sz[x]=1; lt[x]=rt[x]=0;
 60         val[x]=sp;
 61     }
 62     else
 63     {
 64         sz[x]++;
 65         if(sp<val[x]) insert(lt[x],sp);
 66         else insert(rt[x],sp);
 67         maintain(x,sp>=val[x]);
 68     }
 69 }
 70 
 71 inline int del(int &x,int sp)
 72 {
 73     sz[x]--;
 74     if(sp==val[x]||(sp<val[x]&&!lt[x])||(sp>val[x]&&!rt[x]))
 75     {
 76         int y=val[x];
 77         if(!lt[x]||!rt[x]) x=lt[x]+rt[x];
 78         else val[x]=del(lt[x],sp+1);
 79         return y;
 80     }
 81     else
 82     {
 83         if(sp<val[x]) del(lt[x],sp);
 84         else del(rt[x],sp);
 85     }
 86 }
 87 
 88 inline int pred(int &x,int y,int sp)
 89 {
 90     if(!x) return y;
 91     else if(sp>val[x]) return pred(rt[x],x,sp);
 92     return pred(lt[x],y,sp);
 93 }
 94 
 95 inline int succ(int &x,int y,int sp)
 96 {
 97     if(!x) return y;
 98     else if(sp<val[x]) return succ(lt[x],x,sp);
 99     return succ(rt[x],y,sp);
100 }
101 
102 inline void go()
103 {
104     memset(vis,0,sizeof vis);
105     root=cnt=h=0;
106     insert(root,0); insert(root,n+1);
107     char str[10];int da;
108     while(m--)
109     {
110         scanf("%s",str);
111         if(str[0]=='D')
112         {
113             scanf("%d",&da);
114             insert(root,da);
115             q[++h]=da;vis[da]=true;
116         }
117         else if(str[0]=='Q')
118         {
119             scanf("%d",&da);
120             if(vis[da]) {puts("0");continue;}
121             int f1=pred(root,0,da);
122             int f2=succ(root,0,da);
123             printf("%d\n",val[f2]-val[f1]-1);
124         }
125         else
126         {
127             del(root,q[h]);
128             vis[q[h]]=false;
129             h--;
130         }
131     }
132 }
133 
134 int main()
135 {
136     while(scanf("%d%d",&n,&m)!=EOF) go();
137     return 0;
138 }

POJ 3481:

View Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <algorithm>
  5 #include <cstdlib>
  6 
  7 #define N 2000000
  8 
  9 using namespace std;
 10 
 11 int lt[N],rt[N],val[N],bh[N],sz[N];
 12 int n,root,cnt;
 13 
 14 inline void rotate_r(int &x)
 15 {
 16     int y=lt[x];
 17     lt[x]=rt[y];
 18     rt[y]=x;
 19     sz[y]=sz[x];
 20     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 21     x=y;
 22 }
 23 
 24 inline void rotate_l(int &x)
 25 {
 26     int y=rt[x];
 27     rt[x]=lt[y];
 28     lt[y]=x;
 29     sz[y]=sz[x];
 30     sz[x]=sz[lt[x]]+sz[rt[x]]+1;
 31     x=y;
 32 }
 33 
 34 inline void maintain(int &x,int fg)
 35 {
 36     if(!fg)
 37     {
 38         if(sz[lt[lt[x]]]>sz[rt[x]]) rotate_r(x);
 39         else if(sz[rt[lt[x]]]>sz[rt[x]]) rotate_l(lt[x]),rotate_r(x);
 40         else return;
 41     }
 42     else
 43     {
 44         if(sz[rt[rt[x]]]>sz[lt[x]]) rotate_l(x);
 45         else if(sz[lt[rt[x]]]>sz[lt[x]]) rotate_r(rt[x]),rotate_l(x);
 46         else return;
 47     }
 48     maintain(lt[x],0); maintain(rt[x],1);
 49     maintain(x,1); maintain(x,0);
 50 }
 51 
 52 inline void insert(int &x,int sp,int id)
 53 {
 54     if(!x)
 55     {
 56         x=++cnt;
 57         sz[x]=1; lt[x]=rt[x]=0;
 58         val[x]=sp; bh[x]=id;
 59     }
 60     else
 61     {
 62         sz[x]++;
 63         if(sp<val[x]) insert(lt[x],sp,id);
 64         else insert(rt[x],sp,id);
 65         maintain(x,sp>=val[x]);
 66     }
 67 }
 68 
 69 inline int del(int &x,int sp)
 70 {
 71     sz[x]--;
 72     if(val[x]==sp||(sp<val[x]&&!lt[x])||(sp>val[x]&&!rt[x]))
 73     {
 74         int y=x;
 75         if(!lt[x]||!rt[x]) x=lt[x]+rt[x];
 76         else
 77         {
 78             int z=del(lt[x],val[x]+1);
 79             val[x]=val[z]; bh[x]=bh[z];
 80         }
 81         return y;
 82     }
 83     else
 84     {
 85         if(sp<val[x]) del(lt[x],sp);
 86         else del(rt[x],sp);
 87     }
 88 }
 89 
 90 inline int getmin(int x)
 91 {
 92     int res;
 93     for(res=x;lt[res];res=lt[res]);
 94     return res;
 95 }
 96 
 97 inline int getmax(int x)
 98 {
 99     int res;
100     for(res=x;rt[res];res=rt[res]);
101     return res;
102 }
103 
104 inline void go()
105 {
106     int a,b,pd;
107     root=cnt=0;
108     while(scanf("%d",&pd),pd)
109     {
110         if(pd==1)
111         {
112             scanf("%d%d",&a,&b);
113             insert(root,b,a);
114         }
115         else if(pd==2)
116         {
117             int mx=getmax(root);
118             printf("%d\n",bh[mx]);
119             if(mx) del(root,val[mx]);
120         }
121         else
122         {
123             int mn=getmin(root);
124             printf("%d\n",bh[mn]);
125             if(mn) del(root,val[mn]);
126         }
127     }
128 }
129 
130 int main()
131 {
132     go();
133     return 0;
134 }