封装版代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
const int MAXN=100010;
int n;
class Treap
{
public:
Treap(void)
{
rt=cnt=0;
memset(a,0,sizeof a);
memset(s,0,sizeof s);
}
void Insert(int x)
{
_Insert(rt,x);
}
int Xth(int x)
{
return _Xth(rt,x);
}
private:
bool a[MAXN];
int rt,cnt;
struct node
{
int l,r,v,p,size,num;
}s[MAXN];
int Random(void)
{
int x;
while(a[x=rand()%MAXN]);
a[x]=1;
return x;
}
void Update(int i)
{
s[i].size=s[s[i].l].size+s[s[i].r].size+s[i].num;
}
void L_Rotate(int &i)
{
int t=s[i].r;
s[i].r=s[t].l,s[t].l=i;
s[t].size=s[i].size;
Update(i),i=t;
}
void R_Rotate(int &i)
{
int t=s[i].l;
s[i].l=s[t].r,s[t].r=i;
s[t].size=s[i].size;
Update(i),i=t;
}
void _Insert(int &i,int x)
{
if(!i)
{
s[i=++cnt].v=x,s[i].p=Random();
s[i].size=s[i].num=1;
return;
}
++s[i].size;
if(x==s[i].v)
++s[i].num;
else if(x<s[i].v)
{
_Insert(s[i].l,x);
if(s[s[i].l].p>s[i].p)
R_Rotate(i);
}
else
{
_Insert(s[i].r,x);
if(s[s[i].r].p>s[i].p)
L_Rotate(i);
}
}
int _Xth(int i,int x)
{
if(!i)
return 0;
int t;
if(x<=s[s[i].l].size)
return _Xth(s[i].l,x);
else if(x>(t=s[s[i].l].size+s[i].num))
return _Xth(s[i].r,x-t);
else
return s[i].v;
}
}T;
int main(int argc,char *argv[])
{
scanf("%d",&n);
srand((unsigned)time(NULL));
for(int i=1,x;i<=n;++i)
{
scanf("%d",&x);
T.Insert(x);
if(i&1)
printf("%d\n",T.Xth(i+1>>1));
}
return 0;
}
精简版代码
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
const int MAXN=100010;
bool a[MAXN];
int n,rt,cnt;
struct node
{
int l,r,v,p,size,num;
}s[MAXN];
int Random(void)
{
int x;
while(a[x=rand()%MAXN]);
a[x]=1;
return x;
}
void Update(int i)
{
s[i].size=s[s[i].l].size+s[s[i].r].size+s[i].num;
}
void L_Rotate(int &i)
{
int t=s[i].r;
s[i].r=s[t].l,s[t].l=i;
s[t].size=s[i].size;
Update(i),i=t;
}
void R_Rotate(int &i)
{
int t=s[i].l;
s[i].l=s[t].r,s[t].r=i;
s[t].size=s[i].size;
Update(i),i=t;
}
void Insert(int &i,int x)
{
if(!i)
{
s[i=++cnt].v=x,s[i].p=Random();
s[i].size=s[i].num=1;
return;
}
++s[i].size;
if(x==s[i].v)
++s[i].num;
else if(x<s[i].v)
{
Insert(s[i].l,x);
if(s[s[i].l].p>s[i].p)
R_Rotate(i);
}
else
{
Insert(s[i].r,x);
if(s[s[i].r].p>s[i].p)
L_Rotate(i);
}
}
int Xth(int i,int x)
{
if(!i)
return 0;
int t;
if(x<=s[s[i].l].size)
return Xth(s[i].l,x);
else if(x>(t=s[s[i].l].size+s[i].num))
return Xth(s[i].r,x-t);
else
return s[i].v;
}
int main(int argc,char *argv[])
{
scanf("%d",&n);
srand((unsigned)time(NULL));
for(int i=1,x;i<=n;++i)
{
scanf("%d",&x);
Insert(rt,x);
if(i&1)
printf("%d\n",Xth(rt,i+1>>1));
}
return 0;
}