摘要：
普通平衡树板子参考了大佬博客访问空指针会出错，我用了一个nil代替他。-1:*bufs++;}inlinevoidxxx(){for(;;);}constintmxn=1e5+9;intn;#definelchch[0]#definerchch[1]#defineinfstructnode{node*ch[2],*prt;intsiz,cnt,val;inlinevoidup(){siz=cnt+lch-˃siz+rch-˃siz;}}*nil,SS[mxn],*stk[mxn];//stk就是提前申请内存模拟动态分配好像有点鸡肋classspl{public:node*rt;inttop;inlinevoidinit(){forstk[i]=SS+i;top=mxn-1;nil=stk[top--];nil-˃lch=nil-˃rch=nil-˃prt=nil,nil-˃cnt=nil-˃siz=0;rt=newd,rt-˃lch=newd,rt-˃siz=2;}inlinenode*newd{node*p=stk[top--];p-˃lch=p-˃rch=nil,p-˃prt=f;p-˃cnt=p-˃siz=1,p-˃val=v;returnp;}inlinevoidconnect{x-˃prt=f,f-˃ch[k]=x;}inlineintson{returnx==x-˃prt-˃rch;}inlinevoidrotate{node*f=x-˃prt,*g=f-˃prt;intk=son,kk=son;connect,connect;f-˃up(),x-˃up();ifrt=x,rt-˃prt=nil;elseconnect;}inlinevoidsplay{while(x-˃prt!=nil)p=p-˃rch;splay;p=rt-˃lch;p-˃rch=rt-˃rch,rt-˃rch-˃prt=p,p-˃up();stk[++top]=rt;rt=p,rt-˃prt=nil;}inlinenode*find{node*p=rt;while{ifreturnsplay,p;p=p-˃ch[p-˃valch[p-˃valcnt+p-˃lch-˃siz;ifbreak;p=nxt;}returnsplay,res;}inlinenode*kth{++x;node*p=rt;while{intnum=p-˃lch-˃siz;ifreturnsplay,p;ifp=p-˃lch;elsex-=num+p-˃cnt,p=p-˃rch;}}inlinenode*lower{returnkth;}inlinenode*upper{returnkth;}}sp;#undeflch#undefrch#undefinfintmain(){sp.init();scanf;while(n--){into,x;scanf;switch{case1:sp.insert;break;case2:sp.erase;break;case3:printf;break;case4:printf;break;case5:printf;break;case6:printf;break;}}return0;}原来的splay被卡了据我观察，这组数据很多人都跑不
普通平衡树板子
参考了大佬博客
访问空指针会出错，我用了一个nil代替他。（c++是谁设计的我还得把结构体定义在外面真难受）
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define forg(i,x) for(int i=first[x];i;i=nxt[i])
#define uu unsigned
#define fi first
#define se second
#define od(x) ((x)&1)
#define ev(x) (od(x)^1)
#define mi2(x) (1<<(x))
#define scanf a1234=scanf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
int a1234;
char buf[1<<18],*bufs=buf,*buft=buf;
inline int gc(){
return bufs==buft&&(buft=(bufs=buf)+fread(buf,1,1<<18,stdin)),bufs==buft?-1:*bufs++;
}
inline void xxx(){for(;;);}
const int mxn=1e5+9;
int n;
#define lch ch[0]
#define rch ch[1]
#define inf (0x3f3f3f3f)
struct node{
node*ch[2],*prt;
int siz,cnt,val;
inline void up(){siz=cnt+lch->siz+rch->siz;}
}*nil,SS[mxn],*stk[mxn];
//stk就是提前申请内存 模拟动态分配 好像有点鸡肋
class spl{
public:
node*rt;int top;
inline void init(){
for(int i=0;i<mxn;++i)stk[i]=SS+i;
top=mxn-1;
nil=stk[top--];
nil->lch=nil->rch=nil->prt=nil,nil->cnt=nil->siz=0;
rt=newd(inf,nil),rt->lch=newd(-inf,rt),rt->siz=2;
}
inline node*newd(int v,node*f){
node*p=stk[top--];
p->lch=p->rch=nil,p->prt=f;
p->cnt=p->siz=1,p->val=v;
return p;
}
inline void connect(node*x,node*f,int k){
x->prt=f,f->ch[k]=x;
}
inline int son(node*x){return x==x->prt->rch;}
inline void rotate(node*x){
node*f=x->prt,*g=f->prt;
int k=son(x),kk=son(f);
connect(x->ch[k^1],f,k),connect(f,x,k^1);
f->up(),x->up();
if(g==nil)rt=x,rt->prt=nil;else connect(x,g,kk);
}
inline void splay(node*x,node*y=nil){
while(x->prt!=y){
node*f=x->prt,*g=f->prt;
if(g==y)return rotate(x);
if(son(x)^son(f))rotate(x),rotate(x);
else rotate(f),rotate(x);
}
}
inline void insert(int x){
node*p=rt;
while(1){
++p->siz;
if(p->val==x)return ++p->cnt,splay(p);
node*&nxt=p->ch[p->val<x];
if(nxt==nil)return nxt=newd(x,p),splay(nxt);
p=nxt;
}
}
inline void erase(int x){
find(x);
--rt->cnt,--rt->siz;
if(rt->cnt)return;
node*p=rt->lch;
while(p->rch!=nil)p=p->rch;
splay(p,rt);
p=rt->lch;
p->rch=rt->rch,rt->rch->prt=p,p->up();
stk[++top]=rt;
rt=p,rt->prt=nil;
}
inline node*find(int x){
node*p=rt;
while(1){
if(p->val==x)return splay(p),p;
p=p->ch[p->val<x];
}
}
inline int getrk(int x){
node*p=rt,*nxt;
int res=0;
while(1){
nxt=p->ch[p->val<x];
if(p->val<x)res+=p->cnt+p->lch->siz;
if(nxt==nil)break;
p=nxt;
}
return splay(p),res;
}
inline node*kth(int x){
++x;
node*p=rt;
while(1){
int num=p->lch->siz;
if(num<x&&num+p->cnt>=x)return splay(p),p;
if(x<=num)p=p->lch;
else x-=num+p->cnt,p=p->rch;
}
}
inline node*lower(int x){
return kth(getrk(x)-1);
}
inline node*upper(int x){
return kth(getrk(x+1));
}
}sp;
#undef lch
#undef rch
#undef inf
int main(){
sp.init();
scanf("%d",&n);while(n--){
int o,x;scanf("%d%d",&o,&x);
switch(o){
case 1:sp.insert(x);break;
case 2:sp.erase(x);break;
case 3:printf("%d
",sp.getrk(x));break;
case 4:printf("%d
",sp.kth(x)->val);break;
case 5:printf("%d
",sp.lower(x)->val);break;
case 6:printf("%d
",sp.upper(x)->val);break;
}
}
return 0;
}
原来的splay被卡了
据我观察，这组数据很多人都跑不过去，你要不要也试试呢，嘿嘿
为你奉上一份数据生成器
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define forg(i,x) for(int i=first[x];i;i=nxt[i])
#define uu unsigned
#define fi first
#define se second
#define od(x) ((x)&1)
#define ev(x) (od(x)^1)
#define mi2(x) (1<<(x))
#define scanf a1234=scanf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
int a1234;
char buf[1<<18],*bufs=buf,*buft=buf;
inline int gc(){
return bufs==buft&&(buft=(bufs=buf)+fread(buf,1,1<<18,stdin)),bufs==buft?-1:*bufs++;
}
inline void xxx(){for(;;);}
inline int rd(int l,int r){return rand()%(r-l+1)+l;}
int n=5e4;
inline void work(){
printf("%d
",n*2);
for(int i=1;i<=n;++i)printf("1 %d
",i*2);
for(int i=1;i<=n;++i)printf("5 %d
",od(rand())?3:2*n+1);
}
int main(){
srand((uu)time(0));
work();
return 0;
}
说句闲话，有个东西叫输入输出重定向，命令行里使的，比如./a <a.in >a.out可好用了
//被卡的代码
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define forg(i,x) for(int i=first[x];i;i=nxt[i])
#define uu unsigned
#define fi first
#define se second
#define od(x) ((x)&1)
#define ev(x) (od(x)^1)
#define mi2(x) (1<<(x))
#define scanf a1234=scanf
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
int a1234;
char buf[1<<18],*bufs=buf,*buft=buf;
inline int gc(){
return bufs==buft&&(buft=(bufs=buf)+fread(buf,1,1<<18,stdin)),bufs==buft?-1:*bufs++;
}
inline void xxx(){for(;;);}
const int mxn=1e5+9;
int n;
#define lch ch[0]
#define rch ch[1]
#define inf (0x3f3f3f3f)
struct node{
node*ch[2],*prt;
int siz,cnt,val;
inline void up(){siz=cnt+lch->siz+rch->siz;}
}*nil,SS[mxn],*stk[mxn];
class spl{
public:
node*rt;int top;
inline void init(){
for(int i=0;i<mxn;++i)stk[i]=SS+i;
top=mxn-1;
nil=stk[top--];
nil->lch=nil->rch=nil->prt=nil,nil->cnt=nil->siz=0;
rt=newd(inf,nil),rt->lch=newd(-inf,rt),rt->siz=2;
}
inline node*newd(int v,node*f){
node*p=stk[top--];
p->lch=p->rch=nil,p->prt=f;
p->cnt=p->siz=1,p->val=v;
return p;
}
inline void connect(node*x,node*f,int k){
x->prt=f,f->ch[k]=x;
}
inline int son(node*x){return x==x->prt->rch;}
inline void rotate(node*x){
node*f=x->prt,*g=f->prt;
int k=son(x),kk=son(f);
connect(x->ch[k^1],f,k),connect(f,x,k^1);
f->up(),x->up();
if(g==nil)rt=x,rt->prt=nil;else connect(x,g,kk);
}
inline void splay(node*x,node*y=nil){
while(x->prt!=y){
node*f=x->prt,*g=f->prt;
if(g==y)return rotate(x);
if(son(x)^son(f))rotate(x),rotate(x);
else rotate(f),rotate(x);
}
}
inline void insert(int x){
node*p=rt;
while(1){
++p->siz;
if(p->val==x)return ++p->cnt,splay(p);
node*&nxt=p->ch[p->val<x];
if(nxt==nil)return nxt=newd(x,p),splay(nxt);
p=nxt;
}
}
inline void erase(int x){
find(x);
--rt->cnt,--rt->siz;
if(rt->cnt)return;
node*p=rt->lch;
while(p->rch!=nil)p=p->rch;
splay(p,rt);
p=rt->lch;
p->rch=rt->rch,rt->rch->prt=p,p->up();
stk[++top]=rt;
rt=p,rt->prt=nil;
}
inline node*find(int x){
node*p=rt;
while(1){
if(p->val==x)return splay(p),p;
p=p->ch[p->val<x];
}
}
inline node*find1(int x){
node*p=rt,*pres=nil;
int res=-inf-2;
while(p!=nil){
if(p->val==x)return splay(p),p;
if(p->val<x&&p->val>res)res=p->val,pres=p;
p=p->ch[p->val<x];
}
return splay(pres),pres;
}
inline int getrk(int x){
find1(x);
return rt->val==x?rt->lch->siz:rt->cnt+rt->lch->siz;
}
inline node*kth(int x){
++x;
node*p=rt;
int cnt=0;
while(1){
int num=p->lch->siz;
if(num<x&&num+p->cnt>=x)return splay(p),p;
if(x<=num)p=p->lch;
else x-=num+p->cnt,p=p->rch;
}
}
inline node*lower(int x){
return kth(getrk(x)-1);
}
inline node*upper(int x){
return kth(getrk(x+1));
}
}sp;
#undef lch
#undef rch
#undef inf
int main(){
sp.init();
scanf("%d",&n);while(n--){
int o,x;scanf("%d%d",&o,&x);
switch(o){
case 1:sp.insert(x);break;
case 2:sp.erase(x);break;
case 3:printf("%d
",sp.getrk(x));break;
case 4:printf("%d
",sp.kth(x)->val);break;
case 5:printf("%d
",sp.lower(x)->val);break;
case 6:printf("%d
",sp.upper(x)->val);break;
}
}
return 0;
}