[BZOJ1588]营业额统计

Problem

每次给你一个数，找出前面的数与这个数的差的绝对值的最小值

Solution

Splay

Notice

找不到前驱和后继时，会出错。

Code

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define sqz main

#define ll long long

#define reg register int

#define rep(i, a, b) for (reg i = a; i <= b; i++)

#define per(i, a, b) for (reg i = a; i >= b; i--)

#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)

const int INF = 1e9, N = 40000;

const double eps = 1e-6, phi = acos(-1);

ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}

ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();

if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}

void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}

int pre, suf, point = 0, root;

struct node

{

	int val[N + 5], count[N + 5], num[N + 5], son[2][N + 5], parent[N + 5];

	inline void up(int u)

	{

		count[u] = count[son[0][u]] + count[son[1][u]] + num[u];

	}

	void Rotate(int x, int &rt)

	{

		int y = parent[x], z = parent[y];

		int l = (son[1][y] == x), r = 1 - l;

		if (y == rt) rt = x;

		else if (son[0][z] == y) son[0][z] = x;

		else son[1][z] = x;

		parent[x] = z;

		parent[son[r][x]] = y, son[l][y] = son[r][x];

		parent[y] = x, son[r][x] = y;

		up(y);

		up(x);

	}

	void Splay(int x, int &rt)

	{

		while (x != rt)

		{

			int y = parent[x], z = parent[y];

			if (y != rt)

			{

				if ((son[0][z] == y) ^ (son[0][y] == x))

					Rotate(x, rt);

				else Rotate(y, rt);

			}

			Rotate(x, rt);

		}

	}

	void Insert(int &u, int x, int last)

	{

		if (u == 0)

		{

			u = ++point;

			val[u] = x, parent[u] = last, num[u] = count[u] = 1;

			Splay(u, root);

		}

		else

		{

			if (x > val[u]) Insert(son[1][u], x, u);

			else if (x < val[u]) Insert(son[0][u], x, u);

			else if (x == val[u]) num[u]++, count[u]++, Splay(u, root);

		}

	}

	void Delete(int x)

	{

		Splay(x, root);

		if (num[x] > 1)

		{

			num[x]--, count[x]--;

			return;

		}

		if (son[0][x] * son[1][x] == 0) root = son[0][x] + son[1][x];

		else

		{

			int t = son[1][x];

			while (son[0][t] != 0) t = son[0][t];

			Splay(t, root);

			son[0][t] = son[0][x], parent[son[0][x]] = t;

			up(t);

		}

		parent[root] = 0;

	}

	void Find_pre(int u, int x)

	{

	    if (u == 0) return;

	    if (x >= val[u])

	    {

	        pre = u;

	        Find_pre(son[1][u], x);

	    }

	    else Find_pre(son[0][u], x);

	}

	void Find_suf(int u,int x)

	{

	    if (u == 0) return;

	    if (x <= val[u])

	    {

	        suf = u;

	        Find_suf(son[0][u], x);

	    }

	    else Find_suf(son[1][u], x);

	}

	int Find_num(int u, int x)

	{

		if (x <= count[son[0][u]]) return Find_num(son[0][u], x);

		if (x > count[son[0][u]] + num[u]) return Find_num(son[1][u], x - count[son[0][u]] - num[u]);

		return val[u];

	}

	int Find_id(int u, int x)

	{

		if (x == val[u]) return u;

		if (x > val[u]) return Find_id(son[1][u], x);

		if (x < val[u]) return Find_id(son[0][u], x);

	}

}Splay_tree;

int main()

{

    int n = read(), x = read();

    int ans = x;

    Splay_tree.Insert(root, x, 0);

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

    {

    	x = read();

        pre = 0, suf = n + 1;

        Splay_tree.Find_pre(root, x);

        Splay_tree.Find_suf(root, x);

        if (pre == 0) ans += Splay_tree.val[suf] - x;

        else if (suf == n + 1) ans += x - Splay_tree.val[pre];

        else ans += min(x - Splay_tree.val[pre], Splay_tree.val[suf] - x);

        Splay_tree.Insert(root, x, 0);

    }

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

}