题解 P3419 【[POI2005]SAM-Toy Cars】

贪心+线段树

---

另一篇用线段树的题解码风自认为有点奇怪，就写一篇（自认为）码风正常一点的

提供一道弱化版P2088 果汁店的难题题目基本一样，范围小了很多

思路比较简单，就是每次需要将玩具放回架子上时，优先放离下次使用最远的玩具

那么我们先预处理出一个next数组（代码中为nxt），来保存对于每个玩具，下一次使用同样的玩具是什么时候

那么线段树用来维护什么呢？我们用线段树来维护每种玩具下一次使用是什么时候。当然，如果这种玩具不在地上，就不加入线段树的维护（因为我们需要用线段树来维护最大值，所以将这种玩具下一次使用的时间设为0）

这样的话，我们每次要将一个新的玩具放到地上时，就要用线段树来查询离下次使用时间最远的一个玩具，然后放回架子上了！

最后就是代码了，细节还是有一点的，需要注意一下

#include<iostream>
using namespace std;
int nxt[500005],book[500005],a[500005];//book数组辅助处理nxt数组，a为初始数组
bool bj[500005];//bj数组记录玩具是否在地上
int maxx[400005],wz[400005];//线段树数组
void up(int root){
	if((maxx[root<<1])>(maxx[root<<1|1])){
		maxx[root]=maxx[root<<1];
		wz[root]=wz[root<<1];
	}
	else{
		maxx[root]=maxx[root<<1|1];
		wz[root]=wz[root<<1|1];
	}
}
void change(int root,int l,int r,int k,int temp){
	if(l==r){maxx[root]=temp;wz[root]=l;return;}
	int mid=(l+r)>>1;
	if(k<=mid)change(root<<1,l,mid,k,temp);
	else change(root<<1|1,mid+1,r,k,temp);
	up(root);
}
//----以上是线段树板子
int main(){
	int k,q,n,st=0,sum=0;//sum是答案，st记录地上的玩具数目
	cin>>k>>q>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		nxt[book[a[i]]]=i;
		book[a[i]]=i;
	}//处理nxt数组，用book数组记录当种玩具最靠后的位置
	for(int i=1;i<=n;i++)if(nxt[i]==0)nxt[i]=999999999;//如果是同种玩具最后一个，nxt设为inf
	for(int i=1;i<=n;i++){
		if(bj[a[i]]){
			change(1,1,k,a[i],nxt[i]);
			continue;
		}//玩具在地上就直接在线段树上改，然后直接过
		if(st<q){
			st++;
			change(1,1,k,a[i],nxt[i]);
			bj[a[i]]=1;
			sum++;
			continue;
		}//玩具还没放满时直接放，线段树上改
		int x=wz[1];//找到最远的玩具
		change(1,1,k,x,0);//放回架子
		change(1,1,k,a[i],nxt[i]);//当前的拿回地上
		bj[x]=0;
		bj[a[i]]=1;
		sum++;//统计答案
	}
	cout<<sum;
	return 0;
}