大视野1588 splay简单题

题目连接

题意：  给你n个数，要求对于所有的i， 求出第i个数 和1------- i-1之间的数里找一个与第i 个数绝对值差值最小， 求所有的差值之和

做法： 对于第i个数v，把v 插入伸展树，若v存在就不插入，并把v所在的节点旋转到根，在通过根的左右子树找最接近的左右两个数，更新答案即可

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace  std;
struct node;
node *null, *root;
struct node {
	node *c[2], *fa;
	int sz, v;
	inline bool d() {
		return fa->c[1]== this;
	}
	inline void fix(int d, node *x) {
		c[d] = x, x->fa = this;
	}
	inline void rot() {
		node *y = fa, *z = y->fa;
		bool f = d();
		z->fix(y->d(), this);
		y->fix(f, c[!f]);
		fix(!f, y);
		y->up();
	}
	void splay(node *g) {
		while(fa != g) {
			node *y = fa, *z = y->fa;
			if(z == g) rot();
			else if(y->d() == d())
				y->rot(), rot();
			else rot(), rot();
		}
		up();
		if(g==null) root = this;
	}
	void up() {
		sz = c[0]->sz + c[1]->sz+1;
	}
	int cmp(int x) const {
		if(x == v) return -1;
		return x > v;
	}
};
const int maxn = 100005;
node mem[maxn];
int tot;
node* newNode(int v=0, node *fa=null) {
	node *x = &mem[tot++];
	x->v = v, x->fa = fa;
	x->sz = 1, x->c[0] = x->c[1] = null;
	return x;
}
bool ins(node *&o, node *fa, int v, node *&ans) {
	if(o == null) {
		o = newNode(v, fa);
		ans = o;
		return 1;
	}
	int d = o->cmp(v);
	if(d == -1) {
		ans = o;
		return 0;
	}
	return ins(o->c[d], o, v, ans);
}
void init() {
	tot = 0;
	null = new node(), null->sz=0;
	root = null;
}
int pre(node *o) {
	if(o==null) return -1;
	if(o->c[1] != null)
		return pre(o->c[1]);
	return o->v;
}
int suf(node *o) {
	if(o==null) return -1;
	if(o->c[0] != null)
		return suf(o->c[0]);
	return o->v;
}
int main() {
	int n, v;
	scanf("%d%d", &n, &v);
	init();
	root = newNode(v, null);
	int ans = v;
	for(int i = 1; i < n; i++) {
		if(scanf("%d", &v) == -1) v = 0;
		node *x;
		int t;
		t = ins(root, null, v, x);
		x->splay(null);
		if(!t) continue;
		int d = 1e9;
		if((t = pre(x->c[0])) != -1)
			d = min(d, v-t);
		if((t = suf(x->c[1])) != -1)
			d = min(d, t-v);
		ans += d;
	}
	printf("%d\n", ans);
	return 0;
}

大视野1588 splay简单题

原文：http://blog.csdn.net/auto_ac/article/details/19137717