http://www.zybbs.org/JudgeOnline/problem.php?id=1503

这几天在学Splay，果断被虐成傻X……一开始看ZKW的Splay，信心满满写自顶向下的非递归Splay，结果每次写了一半都感觉自己完全看不懂ZKW在干吗，然后全部删掉……

就这么浪费1天之后终于下决心不写自顶向下的Splay了（反正LCT不会用到！），于是自己YY了一个Splay！一开始先交了1588《营业额统计》（这题很久以前用TreapA过，但是现在调用time函数会RE所以……），结果各种WA……改了N久感觉真心没写错啊，于是和自己的Treap对拍，也没错……然后看自己的Treap代码，然后就想起来有人告诉过我这题数据不全……丢失的部分用0来替代就可以了……晕啊……

接着交1503，这题更坑爹！！！也是各种WA整整半天。无奈下找了AC大神的SBT来对拍，发现如果有个员工初始工资低于工资下界，那么这个傻X根本不会来，也就是离开的人数中不算他！！！这是我的语文问题还是出数据的人的语文问题啊！！！这种题考试的时候怎么办啊啊啊！

50+行代码，好长好坑爹……不过挺快的，比CQF说的巨快的SBT快好多……不过比RP不低的Treap还是差了点……

PS:1588HH神犇直接单旋伪splay秒杀，Orz！

接下来要学DLX和LCT……郁闷……

#include <stdio.h>
#include <string.h>
#define maxn 100001
#define lt(a,b) ((a)==(b))
#define rcmp(a,b) ((a)>(b))
#define icmp(a,b) ((a)>=(b))
#define scmp(a,b) ((a)<(b))
typedef struct _Splay{struct _Splay *c[2],*f;int v,s,k;}Splay,*PSplay;
Splay null,st[maxn],*stp=st,*r=&null;
int ans,as,n,m,k;char str[5000000],*p=str,ch;
inline PSplay update(PSplay x){return x->s=x->c[0]->s+x->c[1]->s+x->k,x;}
inline PSplay rot(PSplay x){
	PSplay fx=x->f,ffx=fx->f;
	_Bool c=fx->c[1]==x,fc=ffx->c[1]==fx;
	if(fx!=&null){
		if(fx->c[c]=x->c[!c])fx->c[c]->f=fx;
		if((x->f=ffx)!=&null)ffx->c[fc]=x;
		update((fx->f=x)->c[!c]=fx);
	}return x;
}inline PSplay splay(PSplay x){
	if(x==&null||x->f==&null)return x;
	for(;x->f!=&null;rot(x))if(x->f->f!=&null)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x);
	return update(x);
}inline PSplay Rank(PSplay r,int x){
	_Bool c;
	if(x<=0||r->s<x)return &null;
	for(;;r=r->c[c])if(x>r->c[0]->s&&x<=r->c[0]->s+r->k)return splay(r);else if(c=x>r->c[0]->s)x-=r->c[0]->s+r->k;
}inline PSplay Find(PSplay r,int x){
	PSplay ans=&null;
	for(;r!=&null;r=r->c[rcmp(r->v,x)])if(icmp(r->v,x)&&(ans==&null||scmp(r->v,ans->v)))ans=r;
	return splay(ans);
}inline PSplay Insert(PSplay r,int x){
	for(stp->f=&null;r!=&null;r=(stp->f=r)->c[rcmp(r->v,x)])if(lt(r->v,x)){r->s++,r->k++;return splay(r);}
	stp->v=x;stp->c[0]=stp->c[1]=&null;stp->s=stp->k=1;
	return stp->f==&null?stp++:splay(stp->f->c[rcmp(stp->f->v,x)]=stp++);
}inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')if(!*p++)return -1;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}main(){
	fread(str,1,5000000,stdin);
	n=getint(),m=getint();null.f=null.c[0]=null.c[1]=&null;
	for(r=Insert(r,~0U>>1);n--;){
		ch=*++p;k=getint();
		if(ch=='F'){
			if(r->s<++k)puts("-1");
			else printf("%d\n",(r=Rank(r,k))->v-as);
		}else if(ch=='A')as-=k;
		else if(ch=='I'){if(k>=m)r=Insert(r,k+as);}
		else{
			ans+=(r=Find(r,(as+=k)+m))->c[1]->s;
			r->s-=r->c[1]->s;r->c[1]=&null;
		}
	}return printf("%d\n",ans),0;
}

• inline
• block