P2073题解

链接：P2073 送花

题意：

有若干朵花，每个有两个属性（美丽值和价格）。你需要维护 \(3\) 种操作：

• 1.添加一朵花（如果之前有价格相同的忽略此操作）
• 2.删除最贵的花
• 3.删除最便宜的花
  最后输出两个数：美丽值的总和和价格总和

解法：

经典的平衡树题。
对于第一种操作，关键在于判重。先询问一下有没有价格相同的再加入。

bool ask(int &k,int val){//询问有没有价格为val的花
	bool flag=false;
	int a,b,z;
	a=b=z=0;
	split(k,a,b,val);
	split(a,a,z,val-1);//z树为价值为val的花
	if(z!=0) flag=true;
	merge(a,a,z);
	merge(k,a,b);
	return flag;
}

void insert(int &k,int val,int nice){
	int a,b;
	a=b=0;
	if(ask(root,val)) return;//先判重
	int cur=add_node(val,nice);
	split(k,a,b,val);
	merge(a,a,cur);
	merge(k,a,b);
	ans1+=val;
	ans2+=nice;
	return;
}

对于第二种和第三种操作，都是板子，但是不要忘记在删除之前判断一下树是否为空
全代码：

#include<bits/stdc++.h>
using namespace std;
int tot=0,root=0;
int ans1,ans2;

struct node{
	int lc,rc,size,val,rnk,nice;
}tree[100001];

void update(int k){
	tree[k].size=tree[tree[k].lc].size+tree[tree[k].rc].size+1;
	return;
}

void split(int k,int &a,int &b,int val){
	if(k==0){
		a=b=0;
		return;
	}
	else if(tree[k].val<=val){
		a=k;
		split(tree[k].rc,tree[k].rc,b,val);
	}
	else{
		b=k;
		split(tree[k].lc,a,tree[k].lc,val);
	}
	update(k);
	return;
}

void merge(int &k,int a,int b){
	if(a==0 || b==0){
		k=a+b;
		return;
	}
	else if(tree[a].rnk<tree[b].rnk){
		k=a;
		merge(tree[a].rc,tree[a].rc,b);
	}
	else{
		k=b;
		merge(tree[b].lc,a,tree[b].lc);
	}
	update(k);
	return;
}

int add_node(int val,int nice){
	tree[++tot].val=val;
	tree[tot].nice=nice;
	tree[tot].lc=tree[tot].rc=0;
	tree[tot].size=1;
	tree[tot].rnk=rand();
	return tot;
}

bool ask(int &k,int val){
	bool flag=false;
	int a,b,z;
	a=b=z=0;
	split(k,a,b,val);
	split(a,a,z,val-1);
	if(z!=0) flag=true;
	merge(a,a,z);
	merge(k,a,b);
	return flag;
}

void insert(int &k,int val,int nice){
	int a,b;
	a=b=0;
	if(ask(root,val)) return;
	int cur=add_node(val,nice);
	split(k,a,b,val);
	merge(a,a,cur);
	merge(k,a,b);
	ans1+=val;
	ans2+=nice;
	return;
}

void del(int &k,int val){
	int a,b,z;
	a=b=z=0;
	split(k,a,b,val);
	split(a,a,z,val-1);
	ans1-=tree[z].val;
	ans2-=tree[z].nice;
	merge(k,a,b);
}

int find_num(int k,int x){
	while(tree[tree[k].lc].size+1!=x){
		//cout<<k<<endl;
		if(tree[tree[k].lc].size>=x){
			k=tree[k].lc;
		}
		else{
			x-=(tree[tree[k].lc].size+1);
			k=tree[k].rc;
		}
	}
	return tree[k].val;
}

int main(){
	srand(time(0));
	int a,w,c;
	while(cin>>a){
		if(a==-1) goto to;
		else if(a==1){
			cin>>w>>c;
			insert(root,c,w);
		}
		else if(a==2){
			if(tree[root].size) del(root,find_num(root,tree[root].size));
		}
		else{
			if(tree[root].size) del(root,find_num(root,1));
		}
	}
	to:
	cout<<ans2<<" "<<ans1;
	return 0;
}