BZOJ1528: [POI2005]sam-Toy Cars 贪心+线段树

题解：

万物皆线段树系列。。。

脑补了一个贪心是每次删除玩具时，删除下一次出现最靠后的那个玩具。

但是不会证明，也找不出反例的样子。。。

随便维护维护就过了。

代码：

#include<cctype>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
int getint(){
	int c;
	while(!isdigit(c=getc()));
	int x=c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return x;
}

typedef pair<int,int> pii;
#define mp make_pair
struct SegmentTree{
	pii mx[262144];
	int M;
	void init(int _siz){
		for(M=1;M<(_siz+2);M<<=1);
		for(int i=1;i<(M<<1);++i)
			mx[i]=mp(-1,0);
		for(int i=1;i<=_siz;++i)
			mx[M+i].second=i;
	}
	void modify(int x,int v){
		for(mx[x+=M].first=v,x>>=1;x;x>>=1)
			mx[x]=max(mx[x<<1],mx[x<<1^1]);
	}
	pii query(int tl,int tr){
		pii ans=mp(-1,0);
		for(tl+=M-1,tr+=M+1;tl^tr^1;tl>>=1,tr>>=1){
			if(~tl&1)
				ans=max(ans,mx[tl^1]);
			if(tr&1)
				ans=max(ans,mx[tr^1]);
		}
		return ans;
	}
}Seg;

#define N 100010
#define M 500010
int last[N],nxt[M],a[M];

bool ok[N];
int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n=getint(),m=getint(),q=getint(),i,j;
	for(i=1;i<=q;++i)
		a[i]=getint();
	for(i=q;i>=1;--i){
		nxt[i]=last[a[i]]==0?q+1:last[a[i]];
		last[a[i]]=i;
	}
	int cnt=0,ans=0;
	pii get;
	Seg.init(n);
	for(i=1;i<=q;++i){
		if(!ok[a[i]]){
			++ans;
			if(cnt==m){
				get=Seg.query(1,n);
				ok[get.second]=0;
				Seg.modify(get.second,-1);
			}
			else
				++cnt;
			ok[a[i]]=1;
		}
		Seg.modify(a[i],nxt[i]);
	}
	cout<<ans<<endl;
	return 0;
}