没错这就是让我深陷splay之中的罪魁祸首，昨天打了一下午结果发现是玄学错误的那个
人生第一棵splay平衡树
题目大意：求一段序列，小于当前元素的最大值和大于当前元素的最小值。从该元素前面的元素找。（颓的别人的概括）
题解：
几乎是splay裸题了。
只需要注意一下本身，加一个特判：插入前cnt不为零或者是插入后cnt大于1。（不知道为啥，前者跑了900毫，后者只需要100毫……）
然后我就顺手写了一个小函数判定（其实就是找到该数字对应的下标）
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
struct ing{
int fa,ch[2],data,cnt,size;
}t[200003];
int tot=0,n,dy,root=0,ans=0;
inline void rotate(int x)
{
int y=t[x].fa;
int z=t[y].fa;
int k=t[y].ch[1]==x;
t[x].fa=z;
t[z].ch[t[z].ch[1]==y]=x;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].fa=y;
t[x].ch[k^1]=y;
t[y].fa=x;
}
inline void splay(int x,int goal)
{
while(t[x].fa!=goal)
{
int y=t[x].fa;
int z=t[y].fa;
if(z!=goal)
(x==t[y].ch[0])^(y==t[z].ch[0])?rotate(x):rotate(y);
rotate(x);
}
if(goal==0)root=x;
}
inline void find(int x)
{
int u=root;
if(!u)return ;
while(t[u].ch[x>t[u].data]&&t[u].data!=x)
u=t[u].ch[x>t[u].data];
splay(u,0);
}
inline void insert(int x)
{
int u=root,ff=0;
while(u&&t[u].data!=x)
{
ff=u;
u=t[u].ch[x>t[u].data];
}
if(u) t[u].cnt++;
else
{
u=++tot;
if(ff) t[ff].ch[x>t[ff].data]=u;
t[u].ch[0]=t[u].ch[1]=0;
t[tot].fa=ff;
t[tot].data=x;
t[tot].cnt=1;
t[tot].size=1;
}
splay(u,0);
}
inline int nxt(int x,int f)
{
find(x);
int u=root;
if(t[u].data>x&&f)return u;
if(t[u].data<x&&!f)return u;
u=t[u].ch[f];
while(t[u].ch[f^1])u=t[u].ch[f^1];
return u;
}
inline int dre(int x)
{
int u=root;
while(u&&t[u].data!=x)
u=t[u].ch[x>t[u].data];
return u;
}
int main()
{
// freopen("data.in","r",stdin);
scanf("%d",&n);scanf("%d",&dy);
insert(inf),insert(-inf);
ans+=dy;
insert(dy);
for(register int i=2;i<=n;++i)
{
if(scanf("%d",&dy)==-1)dy=0;
insert(dy);
if(t[dre(dy)].cnt>1) continue;
// cout<<t[nxt(dy,0)].data<<" "<<t[nxt(dy,1)].data<<endl;
ans+=min(abs(t[nxt(dy,0)].data-dy),abs(dy-t[nxt(dy,1)].data));
}
printf("%d
",ans);
return 0;
}
P.S.学习splay推荐https://blog.csdn.net/qq_30974369/article/details/77587168，大佬讲的好清楚（就是留坑没有补，少rank操作）