题解 P2234 【[HNOI2002]营业额统计】

我绝对是Splay的受害者。

代码丑长不说，还特容易毒瘤（身后有一段不得不说的故事）

但还是写出来了呵呵呵…

那就发一发吧

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,root,tot,ans;
struct TREE {
	int lc,rc;
	int ln,rn;
	int fa,data;
} t[40000];
void zig(int x) {
	int y=t[x].fa;
	t[y].lc=t[x].rc;
	if(t[x].rc)t[t[x].rc].fa=y;
	t[x].fa=t[y].fa;
	if(t[y].fa) {
		if(y==t[t[y].fa].lc)t[t[y].fa].lc=x;
		else t[t[y].fa].rc=x;
	}
	t[y].fa=x;
	t[x].rc=y;
	t[y].ln=t[x].rn;
	t[x].rn=t[y].ln+t[y].rn+1;
}
void zag(int x) {
	int y=t[x].fa;
	t[y].rc=t[x].lc;
	if(t[x].lc)t[t[x].lc].fa=y;
	t[x].fa=t[y].fa;
	if(t[y].fa) {
		if(y==t[t[y].fa].lc)t[t[y].fa].lc=x;
		else t[t[y].fa].rc=x;
	}
	t[y].fa=x;
	t[x].lc=y;
	t[y].rn=t[x].ln;
	t[x].ln=t[y].ln+t[y].rn+1;
}
void Splay(int x) {
	int p;
	while(t[x].fa) {
		p=t[x].fa;
		if(t[p].fa==0) {
			if(x==t[p].lc)zig(x);
			else zag(x);
			break;
		}
		if(x==t[p].lc) {
			if(p==t[t[p].fa].lc)zig(p),zig(x);
			else zig(x),zag(x);
		} else {
			if(p==t[t[p].fa].rc)zag(p),zag(x);
			else zag(x),zig(x);
		}
	}
	root=x;
}
int QQ() {
	int p=t[root].lc;
	while(p) {
		if(t[p].rc==0)break;
		p=t[p].rc;
	}
	if(p)return t[p].data;
	return 0x3f3f3f3f;
}
int BackMin() {
	int p=t[root].rc;
	while(p) {
		if(t[p].lc==0)break;
		p=t[p].lc;
	}
	if(p)return t[p].data;
	return 0x3f3f3f3f;
}
int add(int x) {
	int p=root,f;
	while(p) {
		f=p;
		if(x<=t[p].data) {
			t[p].ln++;
			p=t[p].lc;
		} else {
			t[p].rn++;
			p=t[p].rc;
		}
	}
	tot++;
	t[tot].data=x;
	if(root==0) {
		root=tot;
		return x;
	}
	t[tot].fa=f;
	if(x<=t[f].data)t[f].lc=tot;
	else t[f].rc=tot;
	Splay(tot);
	return min(abs(QQ()-x),abs(BackMin()-x));
}
int main() 
{
	int i,j,x;
	cin>>n;
	for(i=1; i<=n; i++) {
		cin>>x;
		ans+=add(x);
	}
	cout<<ans;
	return 0;
}