“如果此时花束中已经有了相等价格的花，那么这朵花不能加入花束”

我看到这句话后就写了个桶数组来标记花的价格，添加花时就看有没有标记，删花时取消标记。结果交上去20分。然后我换了个方法，在添加花的函数内判断花的位置有没有值，结果就AC了。

所以说用桶数组标记花的价格为什么是错的？

20分代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n,m,opt,book[MAXN];
struct node{
	int l,r,mn,mx;
	long long w,c;
}tree[MAXN*4];
void update(int u){
	tree[u].mn=min(tree[u*2].mn,tree[u*2+1].mn);
	tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
	tree[u].w=tree[u*2].w+tree[u*2+1].w;
	tree[u].c=tree[u*2].c+tree[u*2+1].c;
}
void build(int u,int l,int r){
	tree[u].mn=1e6+1;
	tree[u].l=l,tree[u].r=r;
	if(l==r)return;
	int mid=tree[u].l+tree[u].r>>1;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
}
void change(int u,int w,int c){
	if(tree[u].l==tree[u].r){
		tree[u].w=w;
		tree[u].c=c;
		tree[u].mn=tree[u].mx=c;
		return;
	}
	int mid=tree[u].l+tree[u].r>>1;
	if(c<=mid)change(u*2,w,c);
	else change(u*2+1,w,c);
	update(u);
}
void shan(int u,int k){
	if(tree[u].l==tree[u].r){
		tree[u].w=0;
		tree[u].c=0;
		tree[u].mn=1e6+1;
		tree[u].mx=0;
		return;
	}
	int mid=tree[u].l+tree[u].r>>1;
	if(k<=mid)shan(u*2,k);
	else shan(u*2+1,k);
	update(u);
}
int main(){
	build(1,1,1e6);
	while(1){
		scanf("%d",&opt);
		if(opt==1){
			int w,c;
			scanf("%d%d",&w,&c);
			if(book[c])continue;//查标记
			book[c]=1;//添标记
			change(1,w,c);
		}else if(opt==2){
			if(!tree[1].mx)continue;
			shan(1,tree[1].mx);
			book[tree[1].mx]=0;//取消标记
		}else if(opt==3){
			if(tree[1].mn==1e6+1)continue;
			shan(1,tree[1].mn);
			book[tree[1].mn]=0;//取消标记
		}else{
			printf("%lld %lld",tree[1].w,tree[1].c);
			return 0;
		}
	}
	return 0;
}

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+10;
int n,m,opt;
struct node{
	int l,r,mn,mx;
	long long w,c;
}tree[MAXN*4];
void update(int u){
	tree[u].mn=min(tree[u*2].mn,tree[u*2+1].mn);
	tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
	tree[u].w=tree[u*2].w+tree[u*2+1].w;
	tree[u].c=tree[u*2].c+tree[u*2+1].c;
}
void build(int u,int l,int r){
	tree[u].mn=1e6+1;
	tree[u].l=l,tree[u].r=r;
	if(l==r)return;
	int mid=tree[u].l+tree[u].r>>1;
	build(u*2,l,mid);
	build(u*2+1,mid+1,r);
}
void change(int u,int w,int c){
	if(tree[u].l==tree[u].r){
		if(tree[u].w>0)return;//花的位置没有值就直接返回
		tree[u].w=w;
		tree[u].c=c;
		tree[u].mn=tree[u].mx=c;
		return;
	}
	int mid=tree[u].l+tree[u].r>>1;
	if(c<=mid)change(u*2,w,c);
	else change(u*2+1,w,c);
	update(u);
}
void shan(int u,int k){
	if(tree[u].l==tree[u].r){
		tree[u].w=0;
		tree[u].c=0;
		tree[u].mn=1e6+1;
		tree[u].mx=0;
		return;
	}
	int mid=tree[u].l+tree[u].r>>1;
	if(k<=mid)shan(u*2,k);
	else shan(u*2+1,k);
	update(u);
}
int main(){
	build(1,1,1e6);
	while(1){
		scanf("%d",&opt);
		if(opt==1){
			int w,c;
			scanf("%d%d",&w,&c);
			change(1,w,c);
		}else if(opt==2){
			if(!tree[1].mx)continue;
			shan(1,tree[1].mx);
		}else if(opt==3){
			if(tree[1].mn==1e6+1)continue;
			shan(1,tree[1].mn);
		}else{
			printf("%lld %lld",tree[1].w,tree[1].c);
			return 0;
		}
	}
	return 0;
}