送花

题目背景
小明准备给小红送一束花，以表达他对小红的爱意。他在花店看中了一些花，准备用它们包成花束。

题目描述
这些花都很漂亮，每朵花有一个美丽值W，价格为C。

小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：

操作 含义

1 W C 添加一朵美丽值为W，价格为C的花。

3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小红，所以删除最便宜的一朵花。

2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。

-1 完成添加与删除，开始包装花束

若删除操作时没有花，则跳过删除操作。

如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。

请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。

输入格式
若干行，每行一个操作，以-1结束。

输出格式
一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。

输入输出样例
输入 #1复制
1 1 1
1 2 5
2
1 3 3
3
1 5 2
-1
输出 #1复制
8 5
说明/提示
对于20%数据，操作数<=100，1<=W,C<=1000。

对于全部数据，操作数<=100000,1<=W,C<=1000000。

一道平衡树的裸题。

于是我选择用 fhq_treap来做。

因为我们要维护两个信息，一个美丽度，一个价值。所以开两个数组记录即可。由于这道题我们按照价值建立平衡树，而且每次需要找到价值最大的和最小的，于是我们需要按照个数split，又要插入数据，所以要权值split，所以要写两个。

最后dfs一遍，统计答案即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int sw,sc;
int ch[N][2],w[N],c[N],sz[N],pri[N],num,root,x,y,z;
inline void push_up(int p){
	sz[p]=sz[ch[p][0]]+sz[ch[p][1]]+1;
}
inline int new_node(int a,int b){
	sz[++num]=1; w[num]=a; c[num]=b; pri[num]=rand(); return num;
}
void split(int now,int k,int &x,int &y){
	if(!now)	return (void)(x=y=0);
	if(c[now]<=k)	x=now,split(ch[now][1],k,ch[now][1],y);
	else	y=now,split(ch[now][0],k,x,ch[now][0]);
	push_up(now);
}
void split1(int now,int k,int &x,int &y){
	if(!now)	return (void)(x=y=0);
	if(k<=sz[ch[now][0]])	y=now,split1(ch[now][0],k,x,ch[now][0]);
	else	x=now,split1(ch[now][1],k-sz[ch[now][0]]-1,ch[now][1],y);
	push_up(now);	
}
int merge(int x,int y){
	if(!x||!y)	return x+y;
	if(pri[x]<pri[y]){
		ch[x][1]=merge(ch[x][1],y);	push_up(x);	return x;
	}else{
		ch[y][0]=merge(x,ch[y][0]); push_up(y);	return y;
	}
}
inline void del1(){
	split1(root,sz[root]-1,root,y);
}
inline void del2(){
	split1(root,1,x,root);
}
void dfs(int now){
	if(!now)	return ;
	sw+=w[now];	sc+=c[now];
	dfs(ch[now][0]);	dfs(ch[now][1]);
}
signed main(){
	while(1){
		int op;	scanf("%lld",&op);	if(op==-1)	break;
		if(op==2)	del1();
		else if(op==3)	del2();
		else{
			int a,b;	scanf("%lld %lld",&a,&b);
			split(root,b,x,y);	split(x,b-1,x,z);
			if(sz[z]!=0)	root=merge(merge(x,z),y);
			else	root=merge(merge(x,new_node(a,b)),y);
		}
	}
	dfs(root);	printf("%lld %lld\n",sw,sc);
	return 0;
}