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

强烈推荐，原理讲的很清楚。代码我也是学（抄）的大佬的。（之前调试半天过不了样例，突然发现代码这里求的前驱后继是严格的前驱后继，加个等号就可以了）

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1e5+10,INF=0x3f3f3f3f;
int n,ans,a,root,cnt;
struct node{
	int fa;//记录父亲
	int ch[2];//ch[0]表示左儿子，ch[1]表示右儿子
	int val;//记录节点权值
	int size;//记录节点子树大小（包括该节点）
	int cnt;//记录同样权值的元素个数 
}t[N];
bool get(int x)//查询是左节点还是右节点 
{
	return t[t[x].fa].ch[1]==x;//是右儿子返回1，左儿子返回0 
}
void up(int x)
{
	t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt;
}
void rotate(int x)//旋转操作 
{
    int fa=t[x].fa,gfa=t[fa].fa;
	int d1=get(x),d2=get(fa);
	t[fa].ch[d1]=t[x].ch[d1^1];t[t[x].ch[d1^1]].fa=fa;//t[x].ch[d1^1]连到fa上代替x的位置
	t[gfa].ch[d2]=x;t[x].fa=gfa;//x与grandfather连接代替father的位置
	t[fa].fa=x;t[x].ch[d1^1]=fa;//father与x连边，完成一次旋转
    up(fa);up(x);//更新节点子树个数 
}
void splay(int x,int goal)//goal是将x旋转到goal的下面 
{
	while(t[x].fa!=goal)
	{
		int fa=t[x].fa,gfa=t[fa].fa;
		int d1=get(x),d2=get(fa);
		if(gfa!=goal)
		{
			if(d1==d2)rotate(fa);//若在同边，先转father
			else rotate(x); 
		}
		rotate(x);//再旋一次 
	}
	if(goal==0)root=x;//x旋转到了根节点 
}
void insert(int val)
{
	int node=root,fa=0;
	while(node&&t[node].val!=val)
	    fa=node,node=t[node].ch[t[node].val<val];
	if(node)t[node].cnt++;//如果存在，相同数字个数++
	else//新开一个节点 
	{
		node=++cnt;if(fa)t[fa].ch[t[fa].val<val]=node;
		t[node].fa=fa;
		t[node].val=val;
		t[node].cnt=1;
		t[node].size=1;
	} 
	splay(node,0);//新节点旋到根 
}
int find(int val)//查询一个数的排名 
{
	int node=root;
	while(t[node].val!=val&&t[node].ch[t[node].val<val])
	    node=t[node].ch[t[node].val<val];
	return node;
}
int getpre(int val,int kind)//kind==0查前驱，kind==1查后继 
{
	splay(find(val),0);int node=root;
	if(t[node].val<=val&&kind==0)return node;//此时为前驱 
	if(t[node].val>val&&kind==1)return node;//此时为后继
	node=t[node].ch[kind];
	while(t[node].ch[kind^1])
	    node=t[node].ch[kind^1];
	return node;
}
int main()
{
	//freopen("in.txt","r",stdin);
    scanf("%d",&n);
    insert(INF);insert(-INF);
    scanf("%d",&a);insert(a);n--;ans+=a;
    while(n--)
    {
    	scanf("%d",&a);
    	int pre=getpre(a,0),nxt=getpre(a,1);
    	insert(a);ans+=min(abs(t[pre].val-a),abs(t[nxt].val-a));
	}
	printf("%d\n",ans);
	return 0;
}

总结

splay入门。感觉splay贼牛B了，必须掌握。