营业额统计 (平衡树)
以下给出了四种常见平衡树的代码(splay及其他以后加), 运行时间如下表所示
zig/zag Treap | split/merge Treap | STL set | PBDS rb_tree | |
---|---|---|---|---|
无优化 | 220 ms | 520 ms | 375 ms | 605 ms |
O2优化 | 115 ms | 220 ms | 220 ms | 385 ms |
O3优化 | 120 ms | 230 ms | 100 ms | 145 ms |
结论:不支持O3优化的场景下(各种OJ)用zig/zag Treap,支持O3优化的场景下(工程代码)用STL set
zig/zag Treap
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 33010, INF = 0x3f3f3f3f;
int n;
struct Node {
int l, r;
int key, val;
int cnt, size;
}tr[N];
int root, idx;
void pushup(int p) {
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key) {
tr[++idx].key = key;
tr[idx].val = rand();
tr[idx].cnt = tr[idx].size = 1;
return idx;
}
void zig(int &p) {
int q = tr[p].l;
tr[p].l = tr[q].r, tr[q].r = p, p = q;
pushup(tr[p].r), pushup(p);
}
void zag(int &p) {
int q = tr[p].r;
tr[p].r = tr[q].l, tr[q].l = p, p = q;
pushup(tr[p].l), pushup(p);
}
void build() {
get_node(-INF), get_node(INF);
root = 1, tr[1].r = 2;
pushup(root);
if (tr[1].val < tr[2].val) zag(root);
}
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);
}
pushup(p);
}
int get_prev(int &p, int key) {
if (!p) return -INF;
if (tr[p].key > key) return get_prev(tr[p].l, key);
return max(tr[p].key, get_prev(tr[p].r, key));
}
int get_next(int &p, int key) {
if (!p) return INF;
if (tr[p].key < key) return get_next(tr[p].r, key);
return min(tr[p].key, get_next(tr[p].l, key));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
build();
cin >> n;
LL res = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i == 1) res += x;
else res += min(x - get_prev(root, x), get_next(root, x) - x);
insert(root, x);
}
cout << res << endl;
return 0;
}
split/merge Treap
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 33010, INF = 0x3f3f3f3f;
int n;
struct Node {
int l, r;
int key, val;
int size;
}tr[N];
int root, idx;
void pushup(int p) {
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + 1;
}
int get_node(int key) {
tr[++idx].key = key;
tr[idx].val = rand();
tr[idx].size = 1;
return idx;
}
void split(int p, int &a, int &b, int key) {
if (!p) a = b = 0;
else if (tr[p].key <= key) {
a = p;
split(tr[p].r, tr[a].r, b, key);
pushup(p);
} else {
b = p;
split(tr[p].l, a, tr[b].l, key);
pushup(p);
}
}
void merge(int &p, int a, int b) {
if (!a || !b) p = a + b;
else if (tr[a].val > tr[b].val) {
p = a;
merge(tr[p].r, tr[a].r, b);
pushup(p);
} else {
p = b;
merge(tr[p].l, a, tr[b].l);
pushup(p);
}
}
void build() {
int x = get_node(-INF), y = get_node(INF);
root = 1;
merge(root, x, y);
}
void insert(int &p, int key) {
int x = 0, y = 0, z = get_node(key);
split(p, x, y, key);
merge(x, x, z);
merge(p, x, y);
}
int get_key_by_rank(int &p, int rank) {
if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
if (tr[tr[p].l].size + 1 == rank) return tr[p].key;
return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - 1);
}
int get_prev(int &p, int key) {
int x = 0, y = 0;
split(p, x, y, key);
int res = get_key_by_rank(x, tr[x].size);
merge(p, x, y);
return res;
}
int get_next(int &p, int key) {
int x = 0, y = 0;
split(p, x, y, key - 1);
int res = get_key_by_rank(y, 1);
merge(p, x, y);
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
build();
cin >> n;
LL res = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i == 1) res += x;
else res += min(x - get_prev(root, x), get_next(root, x) - x);
insert(root, x);
}
cout << res << endl;
return 0;
}
STL set
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
int n;
set<PII> S;
void build() {
S.insert({-INF, 0});
S.insert({INF, 0});
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
build();
cin >> n;
LL res = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i == 1) res += x;
else {
auto mx = S.lower_bound({x, 0});
res += min(x - prev(mx)->x, mx->x - x);
}
S.insert({x, i});
}
cout << res << endl;
return 0;
}
PBDS rb_tree
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define x first
#define y second
#define rbt(a) tree<a, null_type, less<a>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
int n;
rbt(PII) S;
void build() {
S.insert({-INF, 0});
S.insert({INF, 0});
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
build();
cin >> n;
LL res = 0;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (i == 1) res += x;
else {
auto mx = S.lower_bound({x, 0});
res += min(x - prev(mx)->x, mx->x - x);
}
S.insert({x, i});
}
cout << res << endl;
return 0;
}