_lzh_ @ 2021-02-24 17:00:25
写的Treap,只有20pts,求大佬帮忙看看
#include<bits/stdc++.h>
#define N 1100000
#define r root
#define int long long
using namespace std;
const int maxx=1e9+1;
int root=0,sum=0,m,mm;
int v[N],s[N],n[N],rd[N],ls[N],rs[N];
void more_new(int x)
{
s[x]=s[ls[x]]+s[rs[x]]+n[x];
}
void turn_left(int &x)
{
int a;
a=rs[x];
rs[x]=ls[a];
ls[a]=x;
more_new(x),more_new(a);
x=a;
}
void turn_right(int &x)
{
int a;
a=ls[x];
ls[x]=rs[a];
rs[a]=x;
more_new(x),more_new(a);
x=a;
}
void in(int &x,int f)
{
if(x==0)
{
x=++sum;
s[x]=n[x]=1;
v[x]=f;
rd[x]=rand();
return;
}
if(v[x]==f)
{
n[x]+=1;
s[x]+=1;
return;
}
if(f>v[x])
in(rs[x],f);
else
in(ls[x],f);
if(f>v[x])
{
if(rd[x]<rd[rs[x]])
turn_left(x);
}
else
{
if(rd[x]<rd[ls[x]])
turn_right(x);
}
more_new(x);
}
void out(int &x,int f)
{
if(x==0)return;
if(f<v[x])
{
out(ls[x],f);
}
else if(f>v[x])
{
out(rs[x],f);
}
else if(f==v[x])
{
if(ls[x]==0&&rs[x]==0)
{
n[x]-=1,s[x]-=1;
if(n[x]==0)x=0;
}
else if(ls[x]==0&&rs[x]!=0)
{
turn_left(x);
out(ls[x],f);
}
else if(ls[x]!=0&&rs[x]==0)
{
turn_right(x);
out(rs[x],f);
}
else
{
if(rd[ls[x]]>rd[rs[x]])
{
turn_right(x);
out(rs[x],f);
}
else
{
turn_left(x);
out(ls[x],f);
}
}
}
more_new(x);
}
int rankk(int x,int f)
{
if(x==0)return 0;
if(v[x]==f)
return s[ls[x]]+1;
if(v[x]<f)
return s[ls[x]]+n[x]+rankk(rs[x],f);
if(v[x]>f)
return rankk(ls[x],f);
return 0;
}
int name(int x,int f)
{
if(x==0)return 0;
if(s[ls[x]]>=f)
return name(ls[x],f);
else if(s[ls[x]]+n[x]<f)
return name(rs[x],f-n[x]-s[ls[x]]);
else
return v[x];
}
int before(int x,int f)
{
if(x==0)
return -maxx;
if(v[x]>=f)
return before(ls[x],f);
else
return max(v[x],before(rs[x],f));
}
int after(int x,int f)
{
if(x==0)
return maxx;
if(v[x]<=f)
return after(rs[x],f);
else
return min(v[x],after(ls[x],f));
}
int ans=0,ltt=0;
signed main()
{
// freopen("test.txt","w",stdout);
cin>>m>>mm;
for(int i=1;i<=m;i++)
{
int xxx;
cin>>xxx;
in(r,xxx);
}
for(int i=1;i<=mm;i++)
{
int opt,x;
cin>>opt>>x;
x^=ltt;
if(opt==1)
in(root,x);
if(opt==2)
out(root,x);
if(opt==3)
ltt=rankk(root,x)+1,ans^=ltt;
if(opt==4)
ltt=name(root,x),ans^=ltt;
if(opt==5)
ltt=before(root,x),ans^=ltt;
if(opt==6)
ltt=after(root,x),ans^=ltt;
// cout<<opt<<" "<<x<<endl;
}
cout<<ans;
return 0;
}
by dying @ 2021-02-24 21:22:34
又来了,刚学OI的treap
by peterwuyihong @ 2021-02-24 21:48:17
@lzh
by _lzh_ @ 2021-02-24 21:51:24
@peterwuyihong 谢谢巨佬,我去改改