逆天峰王者 @ 2020-05-02 08:13:35
请问这种写法的splay不加入边界INF和-INF,就会又wrong,又T,请问大佬原因?
刚学splay,希望大佬指点!在此谢过!
#include<bits/stdc++.h>
#define db double
#define RE register
#define ll long long
#define P 1000000007
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define getc(a) scanf("%s",a+1)
#define putl(x) printf("%lld\n",x)
#define rep(i,x,y) for(RE int i=x;i<=y;++i)
#define fep(i,x,y) for(RE int i=x;i>=y;--i)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=2e6+10;
int n,m,last,root,tot,ans;
struct wy
{
int v,f,ch[2],sum,rec;
#define v(x) t[x].v
#define f(x) t[x].f
#define sum(x) t[x].sum
#define rec(x) t[x].rec
#define ch(x,y) t[x].ch[y]
}t[N];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
inline void updata(int x) {sum(x)=sum(ch(x,0))+sum(ch(x,1))+rec(x);}
inline int random(int n){return (ll)rand()*rand()%n;}
inline void retato(int x)
{
int y=f(x),z=f(y),k=ch(y,1)==x;
ch(z,ch(z,1)==y)=x;f(x)=z;
ch(y,k)=ch(x,k^1);f(ch(x,k^1))=y;
ch(x,k^1)=y;f(y)=x;
updata(y);updata(x);
}
inline void splay(int x,int goal)
{
while(f(x)!=goal)
{
int y=f(x),z=f(y);
if(z!=goal) (ch(z,0)==y)^(ch(y,0)==x)?retato(x):retato(y);
retato(x);
}
if(goal==0) root=x;
}
inline int newpoint(int x,int fa)
{
f(++tot)=fa;v(tot)=x;sum(tot)=rec(tot)=1;
return tot;
}
inline void insert(int x)
{
int now=root;
if(!now) {root=newpoint(x,0);return;}
while(1)
{
sum(now)++;
if(v(now)==x) {rec(now)++;splay(now,0);return;}
int next=x>v(now);
if(!ch(now,next))
{
int p=newpoint(x,now);
ch(now,next)=p;
splay(p,0);return;
}
now=ch(now,next);
}
}
inline void find(int x)
{
int now=root;
if(!now) return;
while(v(now)!=x&&ch(now,x>v(now))) now=ch(now,x>v(now));
splay(now,0);
}
inline int Next(int x,int op)
{
find(x);
int now=root;
if(v(now)>x&&op) return now;
if(v(now)<x&&!op) return now;
now=ch(now,op);
while(ch(now,op^1)) now=ch(now,op^1);
return now;
}
inline void delet(int x)
{
int last=Next(x,0),next=Next(x,1);
splay(last,0);splay(next,last);
int now=ch(next,0);
if(rec(now)>1) rec(now)--,splay(now,0);
else ch(next,0)=0;
}
inline int Kth(int x)
{
int now=root;
while(1)
{
int y=ch(now,0);
if(x>sum(y)+rec(now))
{
x-=sum(y)+rec(now);
now=ch(now,1);
}
else if(sum(y)>=x) now=ch(now,0);
else
{
splay(now,0);
return v(now);
}
}
}
int main()
{
//freopen("1.in","r",stdin);
get(n);get(m);
insert(INF*2);insert(-INF*2);
rep(i,1,n)
{
int get(x);
insert(x);
}
rep(i,1,m)
{
int get(opt),get(x);
x^=last;
if(opt==1) insert(x);
else if(opt==2) delet(x);
else if(opt==3)
{
find(x);
last=sum(ch(root,0));
if(v(root)<x) last+=rec(root);
ans^=last;
}
else if(opt==4) last=Kth(x+1),ans^=last;
else if(opt==5) last=v(Next(x,0)),ans^=last;
else if(opt==6) last=v(Next(x,1)),ans^=last;
}
put(ans);
return 0;
}
by Flandre_495 @ 2020-05-02 08:24:06
不加边界的话在删除元素时有可能找不到后继或前驱
by 逆天峰王者 @ 2020-05-02 09:07:29
@Flandre_495
所以问题出在前驱,后继,与删除上了吗??
其他的操作应该没问题吧?
by Flandre_495 @ 2020-05-02 10:01:33
@逆天峰王者 大概吧?
by 逆天峰王者 @ 2020-05-02 10:51:31
@Flandre_495 谢啦,我再调试会.!
by 逆天峰王者 @ 2020-05-02 23:01:41
//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define db double
#define RE register
#define ll long long
#define P 1000000007
#define INF 2000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define getc(a) scanf("%s",a+1)
#define putl(x) printf("%lld\n",x)
#define rep(i,x,y) for(RE int i=x;i<=y;++i)
#define fep(i,x,y) for(RE int i=x;i>=y;--i)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=1e6+10;
int tot,n,m,root,last,ans;
struct wy
{
int ch[2],v,f,sum,rec;
#define ch(x,y) t[x].ch[y]
#define sum(x) t[x].sum
#define rec(x) t[x].rec
#define v(x) t[x].v
#define f(x) t[x].f
}t[N];
inline int read()
{
int x=0,ff=1;
char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*ff;
}
inline void updata(int x){sum(x)=sum(ch(x,0))+sum(ch(x,1))+rec(x);}
inline void retate(int x)
{
int y=f(x),z=f(y),k=ch(y,1)==x;
ch(z,ch(z,1)==y)=x;f(x)=z;
ch(y,k)=ch(x,k^1);f(ch(x,k^1))=y;
ch(x,k^1)=y;f(y)=x;
updata(y);updata(x);
}
inline void splay(int x,int goal)
{
while(f(x)!=goal)
{
int y=f(x),z=f(y);
if(z!=goal) (ch(z,0)==y)^(ch(y,0)==x)?retate(x):retate(y);
retate(x);
}
if(goal==0) root=x;
}
inline void find(int x)
{
int now=root;
if(!now) return;
while(1)
{
if(!now) return;
if(v(now)==x) {splay(now,0);return;}
int next=x>v(now);
now=ch(now,next);
}
}
inline int newpoint(int x,int fa)
{
v(++tot)=x;f(tot)=fa;rec(tot)=sum(tot)=1;
return tot;
}
inline void insert(int x)
{
int now=root;
if(!now) {root=newpoint(x,0);return;}
while(1)
{
sum(now)++;
if(v(now)==x) {rec(now)++;splay(now,0);return;}
int next=x>v(now);
if(!ch(now,next))
{
int p=newpoint(x,now);
ch(now,next)=p;
splay(p,0);return;
}
now=ch(now,next);
}
}
inline void delet(int x)
{
find(x);
int now=root;
if(rec(now)>1) {rec(now)--;sum(now)--;return;}
else if(!ch(now,0)&&!ch(now,1)) {root=0;return;}
else if(!ch(now,0)) {root=ch(now,1);f(ch(now,1))=0;return;}
else
{
int left=ch(now,0);
while(ch(left,1)) left=ch(left,1);
splay(left,now);
ch(left,1)=ch(now,1);f(ch(now,1))=left;
f(left)=0;root=left;
updata(left);
}
}
inline int rank(int x)
{
int now=root,ans=0;
while(1)
{
if(!now) return ans+1;
if(v(now)==x) return ans+sum(ch(now,0))+1;
int next=x>v(now);
if(next) ans+=sum(ch(now,0))+rec(now);
now=ch(now,next);
}
}
inline int kth(int x)
{
int now=root;
while(1)
{
int y=ch(now,0);
if(x>sum(y)+rec(now))
{
x-=sum(y)+rec(now);
now=ch(now,1);
}
else if(sum(y)>=x) now=ch(now,0);
else return v(now);
}
}
inline int lower(int x)
{
int now=root,ans=-INF;
while(1)
{
if(!now) return ans;
if(v(now)<x) ans=max(ans,v(now));
int next=x<=v(now)?0:1;
now=ch(now,next);
}
}
inline int next(int x)
{
int now=root,ans=INF;
while(1)
{
if(!now) return ans;
if(v(now)>x) ans=min(ans,v(now));
int next=x>v(now);
now=ch(now,next);
}
}
int main()
{
// freopen("1.in","r",stdin);
get(n);get(m);
rep(i,1,n)
{
int get(x);
insert(x);
}
rep(i,1,m)
{
int get(op),get(x);
x^=last;
if(op==1) insert(x);
else if(op==2) delet(x);
else if(op==3) ans^=(last=rank(x));
else if(op==4) ans^=(last=kth(x));
else if(op==5) ans^=(last=lower(x));
else if(op==6) ans^=(last=next(x));
}
put(ans);
return 0;
}
//以吾之血,祭吾最后的亡魂
@Flandre_495 这是修改后的,将前驱后继删除都变了,可还是有问题啊??劳烦大佬了...