splay 1296 营业额统计

有一个点超时，确实是个很简单的splay
#include<cstdio>

#include<iostream>

using namespace std;

int n,shu[1000006][2],root,size,b1,b2,sum1,sum[1000005],zhi[1000005];

int fa[1000005];

void xuan(int a1)

{

	int a2,a3,l,r;

	a2=fa[a1];

	a3=fa[a2];

	if(a2==root)

	  root=a1;

	else

	  if(a2==shu[a3][0])

	    shu[a3][0]=a1;

	  else

	    shu[a3][1]=a1;

	if(shu[a2][0]==a1)

	  l=0;

	else

	  l=1;

	r=l^1;

	fa[a1]=a3;

	fa[a2]=a1;

	shu[a2][l]=shu[a1][r];

	shu[a1][r]=a2;

	fa[shu[a2][l]]=a2;

	return;

}

void zhuan(int a1)

{

	int a2,a3;

	for(;a1!=root;)

	  {

	  	a2=fa[a1];

	  	a3=fa[a2];

	  	if(a2!=root)

	  	  if(a2==shu[a3][0]^a1==shu[a2][0])

	  	    xuan(a1);

	  	  else

	  	    xuan(a2);

	  	xuan(a1);

	  }

}

void jia(int &a1,int a2,int a3)

{

	if(a1==0)

	  {

	  	size++;

	  	a1=size;

	  	zhi[a1]=a2;

	  	sum[a1]=1;

	  	fa[a1]=a3;

	  	zhuan(a1);

	  	return;

	  }

	if(zhi[a1]==a2)

	  sum[a1]++;

	else

	  if(zhi[a1]<a2)

	    jia(shu[a1][1],a2,a1);

	  else

	    jia(shu[a1][0],a2,a1);

	return;

}

void qian(int a1,int a2)

{

	if(a1==0)

	  return;

	if(zhi[a1]==a2)

	  b1=a2;

	else

	  if(zhi[a1]<a2)

	    {

	    	b1=zhi[a1];

	    	qian(shu[a1][1],a2);

		}

	  else

	    qian(shu[a1][0],a2);

	return;

}

void hou(int a1,int a2)

{

	if(a1==0)

	  return;

	if(zhi[a1]==a2)

	  b2=a2;

	else

	  if(zhi[a1]>a2)

	    {

	    	b2=zhi[a1];

	    	hou(shu[a1][0],a2);

		}

	  else

	    hou(shu[a1][1],a2);

	return;

}

int main()

{

	scanf("%d",&n);

	scanf("%d",&sum1);

	jia(root,sum1,0);

	for(int i=1;i<n;i++)

	  {

	  	int a1;

	  	scanf("%d",&a1);

	  	b1=-1;

	  	b2=-1;

	  	qian(root,a1);

	  	hou(root,a1);

	  	if(b1==-1)

	  	  sum1+=b2-a1;

	  	else

	  	  if(b2==-1)

	  	    sum1+=a1-b1;

	  	  else

	  	    if(a1-b1<=b2-a1)

	  	      sum1+=a1-b1;

	  	    else

	  	      sum1+=b2-a1;

	  	jia(root,a1,0);

	  }

	printf("%d",sum1);

	return 0;

}
巴特西

splay 1296 营业额统计

最新文章

热门文章
