7KByte @ 2020-03-03 22:32:34
为啥别人的Splay少说50分多的80/90分,我的MLE30?/kel
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 1000005
#define M 100005
using namespace std;
int n,m,u[M],b[N],c[N];
struct node{
int val,sz,fa,son[2],cnt;
}a[N+M];
#define ls a[x].son[0]
#define rs a[x].son[1]
#define F a[x].fa
void link(int x,int y,int which){
a[x].fa=y;a[y].son[which]=x;
}
void updata(int x){
a[x].sz=a[ls].sz+a[rs].sz+a[x].cnt;
}
int son(int x){
return a[F].son[1]==x;
}
#define rt a[0].son[1]
void rotate(int x){
int y=F;
int f=a[y].fa;
int whichx=son(x);
int whichy=son(y);
link(a[x].son[whichx^1],y,whichx);
link(y,x,whichx^1);link(x,f,whichy);
updata(y);updata(x);
}
void splay(int x,int to){
int nd=a[to].fa;
while(F^nd){
if(a[F].fa==nd)rotate(x);
else if(son(F)==son(x))rotate(F),rotate(x);
else rotate(x),rotate(x);
}
}
int tot = 0;
int New(int val){
++tot;
a[tot].son[0]=a[tot].son[1]=a[tot].fa=0;
a[tot].sz=a[tot].cnt=1;a[tot].val=val;
return tot;
}
int build(int l,int r){
if(l>r)return 0;
int mid=(l+r)>>1;
int p=New(b[mid]);
a[p].cnt=c[mid];
link(build(l,mid-1),p,0);
link(build(mid+1,r),p,1);
updata(p);
return p;
}
int rank(int x,int val){
if(!x)return 0;
if(a[x].val==val)return a[ls].sz;
if(a[x].val>val)return rank(ls,val);
return a[ls].sz+a[x].cnt+rank(rs,val);
}
int gval(int x,int rk){
if(!x)return -1;
if(a[ls].sz>=rk)return gval(ls,rk);
if(a[ls].sz+a[x].cnt>=rk)return x;
return gval(rs,rk-a[ls].sz-a[x].cnt);
}
void insert(int x,int val){
if(a[x].val==val)a[x].cnt++;
else if(a[x].val>val){
if(!ls)link(New(val),x,0);
else insert(ls,val);
}
else{
if(!rs)link(New(val),x,1);
else insert(rs,val);
}
updata(x);
}
int remove(int x,int val){
if(a[x].val==val){
if(a[x].cnt){a[x].cnt--;updata(x);return x;}
if(!ls&&!rs)return 0;
if(!ls){
rotate(rs);x=F;
link(remove(ls,val),x,0);
updata(x);
}
else{
rotate(ls);x=F;
link(remove(rs,val),x,1);
updata(x);
}
}
else if(a[x].val>val)link(remove(ls,val),x,0);
else link(remove(rs,val),x,1);
updata(x);return x;
}
int gpre(int val){
int x=rt,ans=0;
while(x){
if(a[x].val>=val)x=ls;
else ans=max(ans,a[x].val),x=rs;
}
return ans;
}
int gnxt(int val){
int x=rt,ans=0x7fffffff;
while(x){
if(a[x].val<=val)x=rs;
else ans=min(ans,a[x].val),x=ls;
}
return ans;
}
void dfs(int x){
if(!x)return;
dfs(ls);
rep(i,1,a[x].cnt)printf("%d ",a[x].val);
dfs(rs);
}
int T=0,size=0;
// By Inf_Voltage
int main(){
srand(time(0));
//freopen("P6136_1.in","r",stdin);
scanf("%d%d",&n,&m);
rep(i,1,n)scanf("%d",&u[i]);
sort(u,u+n+1);
rep(i,0,n)if(!i||u[i]^u[i-1])b[++T]=u[i],c[T]=1;else c[T]++;
size=n+1;
link(build(1,T),0,1);
//cout<<"ss"<<endl;dfs(rt);cout<<"\ntt"<<endl;
int ans=0,pre=0;
rep(i,1,m){
int op,x;scanf("%d%d",&op,&x);
x^=pre;
//cout<<"Start : "<<op<<" "<<x<<endl;
if(op==1)insert(rt,x),splay(tot,rt),size++;
else if(op==2)link(remove(rt,x),0,1),size--;
else{
if(op==3)pre=rank(rt,x);
else if(op==4)pre=gval(rt,x+1),splay(pre,rt),pre=a[pre].val;
else if(op==5)pre=gpre(x);
else pre=gnxt(x);
ans^=pre;
//cout<<pre<<endl;
}
//if(son(rt)!=1)puts("Error");
//cout<<"ss"<<endl;dfs(rt);cout<<"\ntt"<<endl;
//if(tot>1100000){puts("WA");return 0;}
int rd=(rand()<<15)^rand();
if(rand()%103==0)splay(gval(rt,rd%size+1),rt);
}
printf("%d\n",ans);
return 0;
}
by 万万没想到 @ 2020-03-03 22:33:35
Fhq-treap吼啊!
by hly1204 @ 2020-03-03 22:36:37
一般70-100分的splay都正常吧?
by 7KByte @ 2020-03-03 22:45:32
@hly1204 显然是我写假了,已解决
by jyttoby @ 2020-03-03 22:58:58
我也怕不是写了一个假的 Splay