P2234 [HNOI2002]营业额统计

约定不等于承诺〃 2023-06-04 07:59 49阅读 0赞

[题目链接][Link 1]

**平衡树练手题，我们看它这个数列是动态插入的，所以自然而然就会想到用平衡树来维护。平衡树Splay推荐大家看[这篇博客][Link 2]**

**其实差的最小值只有可能是它与其前驱或后继之差，不然就没有更小的了。因为节点是动态插入的，根据Splay的性质，我们为保证复杂度，就会每次将操作节点旋到根，而他的前驱和后继必然就是之前插入过的数。最后将最小值求和即可。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn=1e6+7;
    const int INF=0x7fffffff;
    int ch[maxn][2];
    int n,x;
    int rt,sz;
    int cnt[maxn],fa[maxn],size[maxn],key[maxn];
    int ans;
    void pushup(int x){
        size[x]=size[ch[x][0]]+size[ch[x][1]]+cnt[x];
    }
    bool check(int x){
        return ch[fa[x]][1]==x;
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],who=check(x);
        ch[y][who]=ch[x][who^1];
        fa[ch[y][who]]=y;
        ch[x][who^1]=y;
        fa[y]=x,fa[x]=z;
        if(z) ch[z][ch[z][1]==y]=x;
        pushup(y),pushup(x);
    }
    void splay(int x){
        for(int f;(f=fa[x]);rotate(x)){
            if(fa[f]) rotate((check(f)==check(x))?f:x);
        }
        rt=x;
    }
    void insert(int x){
        if(!rt){
            rt=++sz;
            size[sz]=cnt[sz]=1;
            key[sz]=x;
            return;
        }
        int now=rt,f=0;
        while(1){
            if(x==key[now]){
                cnt[now]++;
                pushup(f); 
                pushup(now);
                splay(now);
                return;
            }
            f=now,now=ch[now][x>key[now]];
            if(!now){
                sz++;
                size[sz]=cnt[sz]=1;
                fa[sz]=f;
                key[sz]=x;
                ch[f][x>key[f]]=sz;
                pushup(f);
                splay(sz);
                return;
            }
        }
    }
    int pre(){
        int now=ch[rt][0];
        if(now==0) return INF;
        while(ch[now][1]) now=ch[now][1];
        return key[now];
    }
    int nxt(){
        int now=ch[rt][1];
        if(now==0) return INF;
        while(ch[now][0]) now=ch[now][0];
        return key[now];
    }
    int main(){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            insert(x);
            if(i==1) ans+=x;
            else{
                if(cnt[rt]>1){
                    ans+=0;    
                } 
                else{
                    int ans1=abs(x-pre());
                    int ans2=abs(x-nxt());
                    ans+=min(ans1,ans2);
                }
            }
        }
        printf("%d\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11346793.html

[Link 1]: https://www.luogu.org/problem/P2234
[Link 2]: https://www.cnblogs.com/LJB666/p/11165921.html
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/6681070a3a054db4adcdbbcec949703e.png