洛谷 P2073 送花
Description
这些花都很漂亮，每朵花有一个美丽值W，价格为C。
小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：
操作 含义
1 W C 添加一朵美丽值为W，价格为C的花。
3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。
2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。
-1 完成添加与删除，开始包装花束
若删除操作时没有花，则跳过删除操作。
如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。
请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。
Input
- 若干行，每行一个操作，以-1结束。
Output
- 一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。
Sample Input
1 1 11 2 521 3 331 5 2-1
Sample Output
8 5
Data Size
对于20%数据，操作数<=100，1<=W,C<=1000。
对于全部数据，操作数<=100000,1<=W,C<=1000000。
题解：
- 平衡树。
- 这题还算是比较模版吧。
- 我比较喜欢这题的操作2和3，可以用比较巧妙的方法解决。用自带的前驱后继函数找到最大/小权值！找最大权值就找inf的前继，找最小权值就找-inf的后继。
- 这样就不用再开一个优先队列或者找第k大了！
- 发现没有，很多题使用平衡树都是在用其灵活的前继后继函数！
#include#include #include #define N 100005#define inf 0x7fffffffusing namespace std;struct T {int l, r, v1, v2, dat;} t[N];int op, root, tot, ans1, ans2;int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}int New(int v1, int v2){ t[++tot].v1 = v1, t[tot].v2 = v2; t[tot].dat = rand(); return tot;}void zig(int &y){ int x = t[y].l; t[y].l = t[x].r, t[x].r = y, y = x;}void zag(int &x){ int y = t[x].r; t[x].r = t[y].l, t[y].l = x, x = y;}void insert(int &p, int v1, int v2){ if(!p) {p = New(v1, v2); return;} if(v1 == t[p].v1) return; if(v1 < t[p].v1) { insert(t[p].l, v1, v2); if(t[t[p].l].dat > t[p].dat) zig(p); } else { insert(t[p].r, v1, v2); if(t[t[p].r].dat > t[p].dat) zag(p); }}bool find(int p, int val){ if(!p) return 0; if(t[p].v1 == val) return 1; if(val < t[p].v1) return find(t[p].l, val); else return find(t[p].r, val);}int preNext(int op, int val){ int ans = op == 0 ? 2 : 1, p = root; while(p) { if(t[p].v1 == val) { if(!op && t[p].l) { p = t[p].l; while(t[p].r) p = t[p].r; ans = p; break; } else if(!op) break; if(op && t[p].r) { p = t[p].r; while(t[p].l) p = t[p].l; ans = p; break; } else if(op) break; } if(!op && t[p].v1 < val && t[p].v1 > t[ans].v1) ans = p; if(op && t[p].v1 > val && t[p].v1 < t[ans].v1) ans = p; p = val < t[p].v1 ? t[p].l : t[p].r; } return t[ans].v1;}void erase(int &p, int val){ if(!p) return; if(val == t[p].v1) { if(t[p].l || t[p].r) { if(!t[p].r || t[t[p].l].dat > t[t[p].r].dat) zig(p), erase(t[p].r, val); else zag(p), erase(t[p].l, val); } else p = 0; return; } val < t[p].v1 ? erase(t[p].l, val) : erase(t[p].r, val);}void dfs(int p){ if(!p) return; if(t[p].v1 != inf && t[p].v1 != -inf) ans1 += t[p].v1; if(t[p].v2 != inf && t[p].v2 != -inf) ans2 += t[p].v2; dfs(t[p].l), dfs(t[p].r);}int main(){ New(inf, inf), New(-inf, -inf), root = 1, t[1].l = 2; while(scanf("%d", &op) == 1) { if(op == -1) break; if(op == 1) { int bea = read(), cos = read(); if(!find(root, cos)) insert(root, cos, bea); } else if(op == 2) { int cos = preNext(0, inf); if(cos != -inf) erase(root, cos); } else if(op == 3) { int cos = preNext(1, -inf); if(cos != inf) erase(root, cos); } } dfs(root); cout << ans2 << ' ' << ans1 << endl; return 0;}