平衡树 Treap set T3
Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。
Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。
分析营业情况是一项相当复杂的工作。
由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。
经济管理学上定义了一种最小波动值来衡量这种情况。
设第 天的营业额为 ，则第 天()的最小波动值 被定义为：
当最小波动值越大时，就说明营业情况越不稳定。
而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。
你的任务就是编写一个程序帮助 Tiger 来计算这一个值。
第一天的最小波动值为第一天的营业额 。
输入格式
第一行为正整数 ，表示该公司从成立一直到现在的天数。
接下来的 行每行有一个整数 (有可能有负数) ，表示第 天公司的营业额。
输出格式
输出一个正整数，表示最小波动值的和。
数据范围
输入样例：
6
5
1
2
5
4
6输出样例：
12样例解释
在样例中，。
思路
求每天最小波动值的总和, 而最小波动值需要求 中使得 最小的值, 也就是距离 最近的值。
且每次找的作用范围只有 , 这样的区间和每次新加一个点似乎可以使用可持久化数据结构, 比如用Tire树, 找和 二进制第k位相同的点, 若没有再找其他的。
不过这里有思路更简单的解法, 即用平衡树维护这个有序数组, 每次先查找 小于等于的最大值, 和 大于等于的最小值, 然后进行对比, 看谁的 最小即可。
也就是说需要实现平衡树的二分查找。可以手写一个也可以用set+lower_bound实现。手写的话需要实现以下几个函数：
- get_node(int key)
- build
- zag / zig 左右旋
- insert(int &p, int key)
- get_prev(int &p, int key)
- 若当前值存在就直接返回, 因为不会有更优解
- get_next(int &p, int key)
- 若当前值存在就直接返回, 因为不会有更优解
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <ctime>
using namespace std;
const int N = 4e4 + 10, INF = 0x3f3f3f3f;
int a[N],idx;
struct Node {
int l,r;
int key, val;
int cnt;
}tr[N];
int root;
int get_node(int key)
{
tr[++idx].key = key;
tr[idx].val = rand();
tr[idx].cnt = 1;
return idx;
}
void zig(int &p) // 右旋
{
int q = tr[p].l;
tr[p].l = tr[q].r;
tr[q].r = p;
p = q;
}
void zag(int &p) // 左旋
{
int q = tr[p].r;
tr[p].r = tr[q].l;
tr[q].l = p;
p = q;
}
void build()
{
get_node(-INF), get_node(INF);
root = 1, tr[root].r = 2;
}
void insert(int &p, int key)
{
if(!p) p = get_node(key);
else if(tr[p].key == key) tr[p].cnt++;
else if(tr[p].key > key)
{
insert(tr[p].l, key);
if(tr[tr[p].l].val > tr[p].val) zig(p);
}
else
{
insert(tr[p].r, key);
if(tr[tr[p].r].val > tr[p].val) zag(p);
}
}
int get_prev(int &p, int key)
{
if(!p) return -INF;
if(tr[p].key == key) return tr[p].key;
if(tr[p].key >= key) return get_prev(tr[p].l, key);
int t = get_prev(tr[p].r, key);
if(abs(key - tr[p].key) < abs(key - t)) return tr[p].key;
return t;
}
int get_next(int &p, int key)
{
if(!p) return INF;
if(tr[p].key == key) return tr[p].key;
if(tr[p].key <= key) return get_next(tr[p].r, key);
int t = get_next(tr[p].l, key);
if(abs(key - tr[p].key) < abs(key - t)) return tr[p].key;
return t;
}
int query(int x) // 查询 1-j 之间的使得 |a[i] - a[j]| 最大的值
{
int v1 = abs(x - get_prev(root, x)), v2 = abs(x - get_next(root, x));
//cout << x << " " << v1 << " " << v2 << endl;
return min(v1,v2);
}
int main()
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
cin >> a[i];
int res = a[1];
insert(root, a[1]);
for(int i = 2; i <= n;i ++)
{
res += query(a[i]);
//cout << "res: " << res << endl;
insert(root, a[i]);
}
cout << res << endl;
return 0;
}