Splay没过样例求调

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e6+5,INF=1e9+5;

int n,a,ans;
bool mark[N],markk[N];
struct node{
	int s[2],f,w;
	int size;
	void init(int _w,int _f)
	{
		w=_w;
		f=_f;
		size=1;
	}
}tree[N];

int read()
{
	int x=0,f=1;
	char c=getchar();
	while (c<'0'||c>'9')
	{
		if (c=='-')
			f=-1;
		c=getchar();
	}
	while (c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

void push_up(int x)
{
	tree[x].size=tree[tree[x].s[0]].size+tree[tree[x].s[1]].size+1;
}

int root,idx;
void rotate(int x)
{
	int y=tree[x].f;
	int z=tree[y].f;
	int k=tree[y].s[1]==x;
	tree[z].s[tree[z].s[1]==y]=x;
	tree[x].f=z;
	tree[y].s[k]=tree[x].s[k^1];
	tree[tree[x].s[k^1]].f=y;
	tree[x].s[k^1]=y;
	tree[y].f=x;
	push_up(y);
	push_up(x);
}

void splay(int x,int k)
{
	while (tree[x].f!=k)
	{
		int y=tree[x].f;
		int z=tree[y].f;
		if (z!=k)
		{
			if ((tree[y].s[1]==x)^(tree[z].s[1]==y))
				rotate(x);
			else
				rotate(y);
		}
		rotate(x);
	}
	if (!k)
		root=x;
}

void insert(int x)
{
	int u=root;
	int f=0;
	while(u&&tree[u].w!=x)
	{
		f=u;
		u=tree[u].s[x>tree[u].w];
	}
	u=++idx;
	if (f)
		tree[f].s[x>tree[f].w]=u;
	tree[u].init(x,f);
	splay(u,0);
}

void find(int x)
{
	int u=root;
	if (!u)
		return ;
	while(tree[u].s[x>tree[u].w]&&x!=tree[u].w)
		u=tree[u].s[x>tree[u].w];
	splay(u,0);
}

int get_next(int x,int f)
{
	find(x);
	int u=root;
	if (tree[u].w>x&&f)
		return u;
	if (tree[u].w<x&&!f)
		return u;
	u=tree[u].s[f];
	while(tree[u].s[f^1])
		u=tree[u].s[f^1];
	return u;
}

signed main()
{
	n=read();
	a=read();
	insert(INF),insert(-INF);
	if (a>=0)
		mark[a]=1;
	else if (a<0)
		markk[-a]=1;
	insert(a);
	ans=a;
	for (int i=2;i<=n;i++)
	{
		a=read();
		if (a>=0&&mark[a])
			continue;
		else{
			mark[a]=1;
			insert(a);
		}
		if (a<0&&markk[-a])
			continue;
		else{
			markk[-a]=1;
			insert(a);
		}
		int q=tree[get_next(a,0)].w;
		int h=tree[get_next(a,1)].w;
		ans+=min(labs(q-a),labs(h-a));
	}
	cout <<ans<<endl;
	return 0;
}

蒟蒻用Splay求前驱以及后继，用特判过相减得0。并且已知多半是get_next出错。