题目背景
小明准备给小万送一束花，以表达他对小万的爱意。他在花店看中了一些花，准备用它们包成花束。
题目描述
这些花都很漂亮，每朵花有一个美丽值W，价格为C。
小明一开始有一个空的花束，他不断地向里面添加花。他有以下几种操作：
操作 含义
1 W C 添加一朵美丽值为W，价格为C的花。
3 小明觉得当前花束中最便宜的一朵花太廉价，不适合送给小万，所以删除最便宜的一朵花。
2 小明觉得当前花束中最贵的一朵花太贵，他心疼自己的钱，所以删除最贵的一朵花。
-1 完成添加与删除，开始包装花束
若删除操作时没有花，则跳过删除操作。
如果加入的花朵价格已经与花束中已有花朵价格重复，则这一朵花不能加入花束。
请你帮小明写一个程序，计算出开始包装花束时，花束中所有花的美丽值的总和，以及小明需要为花束付出的总价格。
输入输出格式
输入格式：
若干行，每行一个操作，以-1结束。
输出格式：
一行，两个空格隔开的正整数表示开始包装花束时，花束中所有花的美丽值的总和。以及小明需要为花束付出的总价格。
输入输出样例
说明
对于20%数据，操作数<=100，1<=W,C<=1000。
对于全部数据，操作数<=100000,1<=W,C<=1000000。
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define ls id<<1 #define rs id<<1|1 using namespace std; const int maxn=1e6+10; const int INF=0x7f7f7f7f; int opt; bool vis[maxn];//用来判重； struct Tree { int l,r; int sumw,sumc; int minn,maxx; }tree[maxn<<2]; void build(int id,int ll,int rr) { tree[id].l=ll,tree[id].r=rr,tree[id].minn=INF; if(ll==rr) return; int m=ll+rr>>1; build(ls,ll,m),build(rs,m+1,rr); } void update(int id,int pos,int val1,int val2,int val3,int val4) { if(tree[id].l==pos && tree[id].r==pos) { tree[id].sumc=val1;tree[id].sumw=val2; tree[id].minn=val3;tree[id].maxx=val4; return; } if(tree[ls].r>=pos) update(ls,pos,val1,val2,val3,val4); else update(rs,pos,val1,val2,val3,val4); tree[id].sumc=tree[ls].sumc+tree[rs].sumc; tree[id].sumw=tree[ls].sumw+tree[rs].sumw; tree[id].minn=min(tree[ls].minn,tree[rs].minn); tree[id].maxx=max(tree[ls].maxx,tree[rs].maxx); } int main() { int n=maxn-10; build(1,1,n); while(scanf("%d",&opt)==1&&opt!=-1) { int w,c; if(opt==1) { scanf("%d%d",&w,&c); if(vis[c]) continue; update(1,c,c,w,c,c); vis[c]=true; } if(opt==3) { if(tree[1].minn==INF) continue;//此时无花 vis[tree[1].minn]=false,update(1,tree[1].minn,0,0,INF,0); } if(opt==2) { if(tree[1].maxx==0) continue; vis[tree[1].maxx]=false,update(1,tree[1].maxx,0,0,INF,0); } } printf("%d %d",tree[1].sumw,tree[1].sumc); }
//题目有毒啊。。 //操作标号给打乱顺序。。。 //害的我一直只能过样例 //太气愤去看了题解 //题解里说题目有毒 //。。。果然 改过标号来之后就A了 //今天重新看了splay //敲题练手 //每个节点四个值， //key是花费，bea是美丽度 //sum是以这个节点为根的子树的美丽度 //cost是以这个节点为根的子树的花费 //最后直接输出根的sum和cost #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=100005; int opt,w,c; struct NODE { NODE *fa; NODE *son[2]; int key,bea; int sum,cost; }node[N]; typedef NODE* Tree; Tree Root,now_node,null; inline int read() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) f=c=='-'?-1:f; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } inline void init() { node->fa=node->son[0]=node->son[1]=node; Root=now_node=null=node; } inline Tree new_node(int key,int bea,Tree fa) { ++now_node; now_node->key=key; now_node->bea=bea; now_node->fa=fa; now_node->son[0]=now_node->son[1]=null; return now_node; } inline bool getgx(Tree root) { return root->fa->son[1]==root; } inline void connect(Tree root,Tree fa,bool flag) { if(fa==null) Root=root; else fa->son[flag]=root; if(root!=null) root->fa=fa; } inline void update(Tree root) { root->sum=root->son[0]->sum+root->son[1]->sum+root->bea; root->cost=root->son[0]->cost+root->son[1]->cost+root->key; } inline void rotate(Tree root) { Tree fa=root->fa; Tree gfa=fa->fa; bool a=getgx(root),b=!a; connect(root->son[b],fa,a); connect(root,gfa,getgx(fa)); connect(fa,root,b); update(fa); update(root); } inline void splay(Tree root,Tree goal) { while(root->fa!=goal) { Tree fa=root->fa; Tree gfa=fa->fa; if(gfa==goal) rotate(root); else if(getgx(root)==getgx(fa)) rotate(fa),rotate(root); else rotate(root),rotate(root); } } inline void insert(int key,int bea) { if(Root==null) Root=new_node(key,bea,null); for(Tree root=Root;root!=null;root=root->son[key>root->key]) { if(key==root->key) { root->sum+=bea; root->cost+=key; splay(root,null); return; } else if(root->son[key>root->key]==null) root->son[key>root->key]=new_node(key,bea,root); root->sum+=bea; root->cost+=key; } } inline void erase(bool flag) { if(Root==null) return; Tree root=Root; for(;;root=root->son[flag]) if(root->son[flag]==null) break; splay(root,null); if(!flag) { Root=root->son[1]; if(Root!=null) Root->fa=null; } else { Root=root->son[0]; if(Root!=null) Root->fa=null; } } int main() { init(); while(opt=read()) { if(opt==-1) break; if(opt==1) { w=read(),c=read(); insert(c,w); } else if(opt==3) erase(0); else erase(1); } printf("%d %d",Root->sum,Root->cost); return 0; }