小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。
这些花都很漂亮，每朵花有一个美丽值W，价格为C。
小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：
操作 含义
1 W C 添加一朵美丽值为W，价格为C的花。
3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。
2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。
-1 完成添加与删除，开始包装花束
若删除操作时没有花，则跳过删除操作。
如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。
请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。
题解：
全程用Treap维护即可。
#include<bits/stdc++.h> using namespace std; const int maxn=2e5+100; const int inf=1e9; typedef long long ll; int w,c; int op; int sum; struct Treap_tree { int ch[2]; int v;//价格 int w;//魅力值 int dat; int size; int cnt; }t[maxn]; int tot; int root; int newNode (int v,int w) { tot++; t[tot].v=v; t[tot].w=w; t[tot].dat=rand(); t[tot].size=1; t[tot].cnt=1; return tot; } void pushup (int x) { t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+t[x].cnt; } void build () { root=newNode(-inf,-inf); t[root].ch[1]=newNode(inf,inf); pushup(root); } void rotate (int &id,int d) { int tt=t[id].ch[d^1]; t[id].ch[d^1]=t[tt].ch[d]; t[tt].ch[d]=id; id=tt; pushup(t[id].ch[d]); pushup(id); } void ins (int &id,int v,int w) { if (!id) { id=newNode(v,w); return; } if (v==t[id].v) return; else { ins(t[id].ch[v>t[id].v],v,w); if (t[id].dat<t[t[id].ch[v>t[id].v]].dat) rotate(id,v<t[id].v); } pushup(id); } void remove (int &id,int v) { if (!id) return; if (v==t[id].v) { if (t[id].ch[0]||t[id].ch[1]) { if (!t[id].ch[1]||t[t[id].ch[0]].dat>t[t[id].ch[1]].dat) { rotate(id,1); remove(t[id].ch[1],v); } else { rotate(id,0); remove(t[id].ch[0],v); } pushup(id); } else id=0; return; } remove(t[id].ch[v>t[id].v],v); pushup(id); } int kth (int id,int k) { if (!id) return inf; if (k<=t[t[id].ch[0]].size) return kth(t[id].ch[0],k); else if (k<=t[t[id].ch[0]].size+t[id].cnt) return t[id].v; else return kth(t[id].ch[1],k-t[t[id].ch[0]].size-t[id].cnt); } pair<ll,ll> bfs (int id) { ll ans1=0,ans2=0; queue<int> q; q.push(id); while (!q.empty()) { int u=q.front(); q.pop(); ans1+=t[u].v; ans2+=t[u].w; if (t[u].ch[0]) q.push(t[u].ch[0]); if (t[u].ch[1]) q.push(t[u].ch[1]); } return make_pair(ans1,ans2); } int main () { sum=0; while (1) { scanf("%d",&op); if (op==1) { scanf("%d%d",&w,&c); ins(root,c,w); } if (op==2) { sum=t[root].size; int Max=kth(root,sum); remove(root,Max); } if (op==3) { int Min=kth(root,1); remove(root,Min); } if (op==-1) break; } pair<ll,ll> ans=bfs(root); printf("%lld %lld ",ans.second,ans.first); }