HYSBZ 1588 营业额统计伸展树

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

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1588
题意:每次查找集合中一个key对于给定的tmp满足 |tmp-key|最小,将tmp加入集合
维护每次的最小差值
第一道伸展树题,大神的模板很好用

代码:

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
const int maxn = 100000 + 50;
typedef long long LL;
const LL INF = 10000000000;
int sroot,root,tot,ch[maxn][2],fa[maxn];
LL key[maxn];/**
**  NewNode
*/
void NewNode(int& rt,int FA,LL k){rt = tot++;fa[rt] = FA;key[rt] = k;ch[rt][0] = ch[rt][1] = 0;
}
/**  kind 0 for zig
**   kind 1 for zag
*/
void rotate(int rt,int kind){int prt = fa[rt];ch[prt][kind] = ch[rt][!kind];fa[ch[rt][!kind]] = prt;if(fa[prt] != sroot){ch[ fa[ prt ] ][ (ch[ fa[ prt ] ][1] == prt) ] = rt;}fa[rt] = fa[prt];ch[rt][!kind] = prt;fa[prt] = rt;
}/** goal sroot for splay rt to root
**  kind 0 left son to zig operation
**  kind 1 right son to zag operation
*/
void Splay(int rt,int goal){while(fa[rt] != goal){//父节点就是目标节点 直接进行一次旋转if(fa[fa[rt]] == goal)rotate(rt,ch[fa[rt]][1] == rt);else{int prt = fa[rt];int kind = (ch[fa[prt]][1] == prt);if(ch[prt][kind] == rt){    //一字型rotate(rt,kind);}else{                       //之字型rotate(rt,!kind);rotate(rt,kind);}}}if(goal == sroot) root = rt;
}int Insert(LL k){int rt = root;while(ch[rt][key[rt] < k]){if(key[rt] == k){Splay(rt,sroot);return 0;}rt = ch[rt][key[rt] < k];}NewNode(ch[rt][key[rt] < k],rt,k);Splay(ch[rt][key[rt] < k],sroot);return 1;
}LL Find_Pre(){int rt = ch[root][0];if(rt == 0) return INF;while(ch[rt][1]) rt = ch[rt][1];return key[rt];
}
LL Find_Next(){int rt = ch[root][1];if(rt == 0) return INF;while(ch[rt][0]) rt = ch[rt][0];return key[rt];
}LL fabs(LL k){return  k > 0 ? k : -k;
}
int main(){int n;while( ~sf("%d",&n) ){sroot = root = 0,fa[0] = 0;ch[root][0] = ch[root][1] = 0;LL tmp,ans = 0;tot = 1;sf("%lld",&tmp);Insert(tmp);
//        pf("Start:\n");ans += tmp;for(int i = 1;i < n;++i){sf("%lld",&tmp);if(!Insert(tmp)) continue;else{ans += min(fabs(tmp - Find_Next()),fabs(tmp - Find_Pre()));}
//            pf("tmp = %lld key %lld\n",tmp,key[root]);}pf("%lld\n",ans);}return 0;
}