营业额统计 splayTree

本文主要是介绍营业额统计 splayTree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

点击打开链接

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define inf 1000000000
using namespace std;
const int maxn=100005;
struct SplayTree
{int son[maxn][2],pre[maxn],val[maxn];int rt,sz;void newNode(int y,int& x,int a) {x=++sz;pre[x]=y;val[x]=a;son[x][0]=son[x][1]=0;}void init() {sz=0;newNode(0,rt,-inf);newNode(rt,son[rt][1],inf);}void Rotate(int x,int c) {int y=pre[x];son[y][!c]=son[x][c];pre[son[x][c]]=y;pre[x]=pre[y];if(pre[x])son[pre[y]][son[pre[y]][1]==y]=x;son[x][c]=y;pre[y]=x;}void Splay(int x,int goal) {while(pre[x]!=goal) {if(pre[pre[x]]==goal) {if(son[pre[x]][0]==x)Rotate(x,1);elseRotate(x,0);}else {int y=pre[x],z=pre[y];if(son[z][0]==y) {if(son[y][0]==x) {Rotate(y,1);Rotate(x,1);}else {Rotate(x,0);Rotate(x,1);}}else {if(son[y][1]==x) {Rotate(y,0);Rotate(x,0);}else {Rotate(x,1);Rotate(x,0);}}}}if(goal==0)rt=x;}void Insert(int a) {int x=rt;while(son[x][val[x]<a])x=son[x][val[x]<a];newNode(x,son[x][val[x]<a],a);Splay(sz,0);}int getMax(int a) {int x=rt;int Max=-inf;while(x) {if(val[x]==a)return a;if(val[x]<a)Max=max(Max,val[x]);if(a>val[x]) {x=son[x][1];}else {x=son[x][0];}}return Max;}int getMin(int a) {int x=rt;int Min=inf;while(x) {if(val[x]==a)return a;if(val[x]>a)Min=min(Min,val[x]);if(a>val[x]) {x=son[x][1];}else {x=son[x][0];}}return Min;}
}spt;
int n,a;
int main()
{spt.init();scanf("%d",&n);int ans=0;scanf("%d",&a);ans+=a;spt.Insert(a);n--;for(int i=0;i<n;i++) {scanf("%d",&a);ans=ans+min(abs(a-spt.getMin(a)),abs(a-spt.getMax(a)));spt.Insert(a);}printf("%d\n",ans);return 0;
}

这篇关于营业额统计 splayTree的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---