[bzoj 1588] [HNOI2002]营业额统计

题意：给一个数列，求 维护1~i项的集合，二分查找不大于a[i]的最大数和不小于a[i]的最小数即可。然而题目并没有给n的范围......经过尝试，我们发现这样可以通过本题。集合用std::set就好，既然要练习Treap，便又手写了一棵平衡树。

// std::set 292ms
#include <cstdio>
#include <set>
#include <functional>
#include <algorithm>
using namespace std;
const int inf = (1LL<<31)-1;
int main()
{
	int n, ans;
	set<int> S;
	set<int, greater<int> > T;
	scanf("%d %d", &n, &ans);
	--n;
	S.insert(ans);
	T.insert(ans);
	while (n--) {
		int x, d = inf;
		scanf("%d", &x);
		set<int>::iterator ix = S.lower_bound(x);
		if (ix != S.end())
			d = min(d, *ix - x);
		set<int, greater<int> >::iterator iy = T.lower_bound(x);
		if (iy != T.end())
			d = min(d, x - *iy);
		ans += d;
		S.insert(x);
		T.insert(x);
	}
	printf("%d\n", ans);
	return 0;
}

{% raw %}
// Treap 208ms
#include <cstdio>
#include <algorithm>
#include <cstdlib>
typedef long long ll;

const int MAX_N = 1e5 + 1, inf = (1LL<<31)-1;

struct Node {
	Node* ch[2];
	int v, r;
} nodes[MAX_N], * null = nodes, * root = null;

namespace Treap {
	Node* new_node(int v)
	{
		static Node* cur = nodes + 1;
		*cur = (Node){{null, null}, v, rand()};
		return cur++;
	}

	inline void rotate(Node* &x, int d)
	{
		Node* y = x->ch[d];
		x->ch[d] = y->ch[d^1];
		y->ch[d^1] = x;
		x = y;
	}

	void insert(Node* &x, int v)
	{
		if (x == null)
			x = new_node(v);
		else if (x->v != v) {
			int d = v > x->v;
			insert(x->ch[d], v);
			if (x->ch[d]->r > x->r)
				rotate(x, d);
		}
	}

	int pre(Node* x, int v)
	{
		Node* y = null;
		while (x != null) {
			if (x->v == v)
				return v;
			if (v < x->v)
				x = x->ch[0];
			else {
				y = x;
				x = x->ch[1];
			}
		}
		return y == null ? -inf : y->v;
	}

	int suc(Node* x, int v)
	{
		Node* y = null;
		while (x != null) {
			if (x->v == v)
				return v;
			if (v > x->v)
				x = x->ch[1];
			else {
				y = x;
				x = x->ch[0];
			}
		}
		return y == null ? inf : y->v;
	}
}

int main()
{
	using namespace Treap;
	srand(65535);
	int n, ans;
	scanf("%d %d", &n, &ans);
	insert(root, ans);
	--n;
	while (n--) {
		int x;
		scanf("%d", &x);
		ans += std::min((ll)x - pre(root, x), suc(root, x) - (ll)x);
		insert(root, x);
	}
	printf("%d\n", ans);
	return 0;
}
{% endraw %}