洛谷 P2073 送花
无旋\(treap\) (\(fhq-treap\))
这道题有点小变化。
对于 \(insert\) 操作,就按花的价格分裂。判断是否有当前要插入的花的价格,如果有就直接合并回去,如果没有,就把当前花插入进去。
对于删除操作,我们就删除点 1,或点 tot。(显然一个最大,一个最小,删哪个根据题意)
这时我们要再写一个分裂函数,按子树大小分裂,然后不用合并了,相当于删除了,具体看代码吧。
注意:按子树大小分裂时,子树的根有点变化。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #define ls(x) t[x].ch[0] #define rs(x) t[x].ch[1] #define ll long long using namespace std; const ll N = 1e5 + 10; struct Tree{ ll ch[2], siz, val, wei, cost; }t[N]; ll n, m, tot, root; ll a, b, c; ll ans1, ans2; inline void pushup(ll x){ t[x].siz = t[ls(x)].siz + t[rs(x)].siz + 1; } inline void split(ll x, ll k, ll &a, ll &b){ if(!x){ a = b = 0; return; } if(t[ls(x)].siz >= k){ b = x; split(ls(x), k, a, ls(x)); pushup(x); }else{ a = x; split(rs(x), k - t[ls(x)].siz - 1, rs(x), b); pushup(x); } } inline void split2(ll x, ll k, ll &a, ll &b){ if(!x){ a = b = 0; return; } if(t[x].cost <= k){ a = x; split2(rs(x), k, rs(x), b); }else{ b = x; split2(ls(x), k, a, ls(x)); } pushup(x); } inline ll newnode(ll val, ll cost){ t[++tot].val = val, t[tot].cost = cost; t[tot].siz = 1, t[tot].wei = rand(); return tot; } inline ll merge(ll x, ll y){ if(!x || !y) return x + y; if(t[x].wei < t[y].wei){ rs(x) = merge(rs(x), y); pushup(x); return x; }else{ ls(y) = merge(x, ls(y)); pushup(y); return y; } } inline void insert(ll w, ll cost){ split2(root, cost, a, b); split2(a, cost - 1, a, c); if(t[c].siz) root = merge(a, merge(c, b)); else root = merge(a, merge(newnode(w, cost), b)); } void dfs(ll x){ if(!x) return; ans1 += t[x].val; ans2 += t[x].cost; dfs(ls(x)), dfs(rs(x)); } signed main(){ ll op, w, cost; while(scanf("%lld", &op)){ if(op == -1) break; if(op == 1) { scanf("%lld%lld", &w, &cost); insert(w, cost); } if(op == 2) split(root, t[root].siz - 1, root, a); if(op == 3) split(root, 1, a, root); } dfs(root); printf("%lld %lld\n", ans1, ans2); return 0; }