洛谷 P2234 [HNOI2002]营业额统计

题意简述

对于每个数，求它在之前的数中的前驱与后继与它的差得最小值

题解思路

平衡树

代码

#include <cstdio>
#include <algorithm>
const int INF=0x3f3f3f3f;
int n,opt,x,res,ans,x1,x2,N;
int a[50000],b[50000];
bool used[1000010];
inline int _abs(const int& x) { return x>0?x:-x; }
struct Node {
    int va,sum,n;
    Node *son[2];
    Node(int x=0) { va=x; sum=n=1; son[0]=son[1]=0; }
    int get(const bool& f) { return son[f]?son[f]->sum:0; }
    void update() { sum=n+get(0)+get(1); }
    int find(const int& x) { return x==va?-1:x>va; }
}*r;
inline void rotate(Node* &o,const bool& f) {
    Node *t=o->son[!f]; o->son[!f]=t->son[f]; t->son[f]=o;
    o->update(); t->update(); o=t;
}
void splay(Node* &o,int x) {
    if(!o) return;
    int f=o->find(x); if(f==-1) return;
    Node* &t=o->son[f]; int f1=t->find(x);
    if(f1!=-1) {
        splay(t->son[f1],x);
        f^f1?rotate(t,f):rotate(o,!f);
    }
    rotate(o,!f);
}
void ins(Node* &o,const int& x) {
    if(!o) { o=new Node(x); return; }
    if(o->find(x)==-1) { ++o->n; o->update(); return; }
    ins(o->son[o->find(x)],x); o->update();
}
void pre(Node* o,const int& x) {
    if (!o) return;
    if (o->va<x) { res=std::max(res,o->va); pre(o->son[1],x); }
    else pre(o->son[0],x);
}
void suc(Node* o,const int& x) {
    if (!o) return;
    if (o->va>x) { res=std::min(res,o->va); suc(o->son[0],x); }
    else suc(o->son[1],x);
}
int main() {
    scanf("%d",&n);
    for (register int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i];
    std::sort(b+1,b+n+1); N=std::unique(b+1,b+n+1)-b-1;
    x=std::lower_bound(b+1,b+n+1,a[1])-b; ins(r,x); ans=b[x]; used[x]=1;
    for (register int i=2;i<=n;++i) {
        x=std::lower_bound(b+1,b+n+1,a[i])-b;
        if (!used[x]) {
            res=-INF; pre(r,x); x1=res^-INF?_abs(b[res]-b[x]):INF;
            res=INF; suc(r,x); x2=res^INF?_abs(b[res]-b[x]):INF;
            ans+=std::min(x1,x2);
            ins(r,x); splay(r,x);
            used[x]=1;
        }
    }
    printf("%d\n",ans);
}

洛谷 P2234 [HNOI2002]营业额统计

原文：https://www.cnblogs.com/xuyixuan/p/11298133.html