[HNOI 2002]营业额统计

题意

给定n次操作，每次加入一个新数字，并向答案累加其前驱/后继和其差的较小值。

思路

平衡树裸题，而且我们只需要添加，不需要删除，支持查找前驱，后继。
所以说想法很暴，写起来难度也不大。

代码

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int INF=0x3f3f3f3f;
struct Node{Node *ch[2];int r,v;int cmp(int x) const {if(x==v) return -1;return x>v;}
};
void Rotate(Node* &o, int d) {Node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;o=k;
}
bool Contain(Node* o, int x) {while(o!=NULL) {int d=o->cmp(x);if(d==-1) return true;else o=o->ch[d];}return false;
}
void Insert(Node* &o,int x) {if(Contain(o,x)) return;if(o==NULL) {o=new Node();o->ch[0]=o->ch[1]=NULL;o->v=x;o->r=rand();}else{int d=o->cmp(x);Insert(o->ch[d],x);if(o->ch[d]->r>o->r) Rotate(o, d^1);}
}
int findmax(Node* o, int x) {if (o==NULL) return INF;if (x>=o->v) return findmax(o->ch[1],x);else return min(o->v,findmax(o->ch[0],x));
}
int findmin(Node* o, int x) {if (o==NULL) return -INF;if (x<=o->v) return findmin(o->ch[0],x);else return max(o->v,findmin(o->ch[1],x));
}
Node *tree;
int main() {int n;scanf("%d", &n);int ans=0;for(int i=1; i<=n; i++) {int x; scanf("%d", &x);if(Contain(tree, x)) continue;Insert(tree, x);int mx=findmax(tree, x);int mn=findmin(tree, x);if(mx+mn==0) ans+=x;else ans+=min(abs(x-mx),abs(x-mn));}printf("%d\n", ans);return 0;
}