[BZOJ2947]促销（Splay）

Description

Great Bytelandish的超级市场网络请你编写一个程序模拟促销商品的成本费用(simulating costs of the promotionbeing prepared)。推销商品要遵守以下规则：

1． 想参与促销的顾客在自己的帐单上写下个人信息，然后将票据投入一个特制的投票箱中。

2． 促销期间，每天结束后，有2张票据将被取出——消费金额最大的和最小的两张帐单。消费金额最大的那位顾客得到的奖品价值等于取出的2张帐单的差额。

3． 为了避免多次得奖，所有取出的帐单将不再放回箱中，其余的票继续参加促销活动.

由于商场的顾客特别多，所以每天投票箱中都至少有2张帐单。你的任务是计算在促销期间，商家一共要送出多少前的礼品。

Code

#include <cstdio>

#include <algorithm>

#define N 1000010

#define lc(x) T[(x)][0]

using namespace std;

int T[N][2],fa[N],k[N],tot,rt,Ans;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

void rotate(int p){

	int q=fa[p],y=fa[q],x=(T[q][1]==p);

	T[q][x]=T[p][x^1];fa[T[q][x]]=q;

	T[p][x^1]=q;fa[q]=p;

	fa[p]=y;

	if(y){

		if(T[y][0]==q) T[y][0]=p;

		else if(T[y][1]==q) T[y][1]=p;

	}

}

void splay(int x){

	for(int y;y=fa[x];rotate(x))

		if(fa[y]) rotate((x==lc(y))==(y==lc(fa[y]))?y:x);

	rt=x;

}

void Insert(int x,int v){

	if(!rt){

		rt=++tot;

		T[rt][0]=T[rt][1]=0;

		fa[rt]=0;

		k[rt]=v;

		return;

	}

	int y;

	for(;;){

		y=T[x][k[x]<v];

		if(!y){

			y=++tot;

			k[y]=v;

			T[y][0]=T[y][1]=0;

			fa[y]=x;

			T[x][k[x]<v]=y;

			break;

		}

		x=y;

	}

	splay(y);

}

void Del(int x){

	splay(x);

	if(T[x][0]*T[x][1]==0) rt=T[x][0]+T[x][1];

	else{

		int t=T[x][1];

		while(T[t][0]) t=T[t][0];

		T[t][0]=T[x][0],fa[T[t][0]]=t;

		rt=T[x][1];

	}

	fa[rt]=0;

}

int f(int x,int b){

	while(T[x][b]) x=T[x][b];

	int r=k[x];

	Del(x);

	return r;

}

int main(){

	int day=read();

	while(day--){

		int n=read();

		while(n--) Insert(rt,read());

		Ans+=f(rt,1)-f(rt,0);

	}

	printf("%d\n",Ans);

	return 0;

}