bzoj 1208 splay模板题2

自己yy了找前驱和后继,学了学怎么删除。。。(反正就是练模板)

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 80005
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define inf 0x3f3f3f3f
using namespace std;
int n,k[N*],size,ch[N*][],root,cnt,fa[N];
void rotate(int p)
{
int q=fa[p],y=fa[q],x=(ch[q][]==p);
ch[q][x]=ch[p][x^];fa[ch[q][x]]=q;
ch[p][x^]=q;fa[q]=p;
fa[p]=y;
if(y)
{
if(ch[y][]==q)ch[y][]=p;
else ch[y][]=p;
}
}
void splay(int x)
{
for(int y;y=fa[x];rotate(x))
{
if(fa[y])
{
if((y==lc(fa[y])&&x==lc(y))||(y==rc(fa[y])&&x==rc(y)))rotate(y);
else rotate(x);
}
}
root=x;
}
void insert(int x,int v)
{
while(ch[x][k[x]<v])x=ch[x][k[x]<v];
ch[x][k[x]<v]=++cnt;
fa[cnt]=x;k[cnt]=v;splay(cnt);
}
int now1,now2;
int pre(int x,int v)
{
int tmp=-inf;
while(ch[x][k[x]<v])
{
if(k[x]<=v)if(k[x]>tmp)tmp=k[x],now1=x;
x=ch[x][k[x]<v];
}if(k[x]<=v)if(k[x]>tmp)tmp=k[x],now1=x;
return tmp;
}
int suc(int x,int v)
{
int tmp=inf;
while(ch[x][k[x]<v])
{
if(k[x]>=v)if(k[x]<tmp)tmp=k[x],now2=x;
x=ch[x][k[x]<v];
}if(k[x]>=v)if(k[x]<tmp)tmp=k[x],now2=x;
return tmp;
}
void del(int x)
{
splay(x);
if(!ch[x][])fa[ch[x][]]=,root=ch[x][];
else if(!ch[x][])fa[ch[x][]]=,root=ch[x][];
else
{
fa[ch[x][]]=;
int tmp=ch[x][];while(ch[tmp][])tmp=ch[tmp][];
splay(tmp);
ch[tmp][]=ch[x][];fa[ch[x][]]=tmp;
}
return ;
}
int main()
{
scanf("%d",&n);
cnt=;root=;
k[]=inf;int ans=;
insert(root,-inf);
size=;int shu=;
for(int i=;i<=n;i++)
{
int t1,t2;scanf("%d%d",&t1,&t2);
if(!t1)
{
if(!shu||size==)
{
insert(root,t2);
shu=;size++;
}
else
{
size--;
int qq=pre(root,t2),ww=suc(root,t2);
if(abs(qq-t2)<=abs(ww-t2))
{
ans+=abs(qq-t2);del(now1);
}
else
{
ans+=ww-t2;del(now2);
}
}
}
else
{
if(shu||size==)
{
insert(root,t2);
shu=;size++;
}
else
{
size--;
int qq=pre(root,t2),ww=suc(root,t2);
if(abs(qq-t2)<=abs(ww-t2))
{
ans+=abs(qq-t2);del(now1);
}
else
{
ans+=ww-t2;del(now2);
}
}
}
ans%=;
}
printf("%d\n",ans);
return ;
}
上一篇:iOS: How To Make AutoLayout Work On A ScrollView


下一篇:MVC准备前基础知识