「题解」：[splay]营业额统计

梦里梦外; 2021-11-04 13:14 198阅读 0赞

没错这就是让我深陷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\n",ans);
        return 0;
    }

P.S.学习splay推荐https://blog.csdn.net/qq\_30974369/article/details/77587168，大佬讲的好清楚（就是留坑没有补，少rank操作）

转载于:https://www.cnblogs.com/xingmi-weiyouni/p/11014450.html