题面

解题思路

优先队列&贪心

分析

一开始给的数据范围过大，先离散化 $\to$ 直接上板子
接着有显然的结论，删去 $Cache$ 中再出现的位置最后的元素是最优的，只要用 维护即可

如何证明贪心的正确性

真·显然，如果删去再出现位置较前的，当做到这个位置 $i$ 时需要重新加入一次，而删去较后的元素，在 $i$ 位置时，就不需要重新加入

关于优先队列

优先队列维护最大值可以说是静态的，当比较的关键字在外部改变时，优先队列内部是不会做出调整的
比如，优先队列中比较关键字为 f[x]，如果 f[x] 在该元素插入之后改变，该元素在优先队列内部的顺序不会改变
不仅如此，随之带来的一系列迷之操作根本停不下来

warning

就算一个值已经出现在了 $Cache$ 中，相应的信息也要更新

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 1000007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return (a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return (a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int n,m,t,p[N],b[N],f[N],ls[N],ans;
bool vis[N];
struct cmp{
    inline bool operator() (const int a,const int b) {
        return f[a]<f[b];
    }
};
priority_queue<int,vector<int>,cmp>P;//重载运算符，根据一个元素下一次出现的位置
int main()
{
    rint i;n=read(),m=read();
    for(i=1;i<=n;i++) p[i]=b[i]=read();
    sort(p+1,p+n+1),t=unique(p+1,p+n+1)-p-1;
    for(i=1;i<=n;++i) b[i]=lower_bound(p+1,p+t+1,b[i])-p;//离散化
    memset(ls,inf,(t+1)<<2);
    for(i=n;i;--i) f[i]=ls[b[i]],ls[b[i]]=i;//下一次出现的位置
    for(i=1,t=0;i<=n;i++) {
        if(vis[b[i]]) {P.push(i);continue;}//存在于Cache中也要更新
        if(t<m) ++t;
        else vis[b[P.top()]]=0,P.pop();
        ++ans,vis[b[i]]=1,P.push(i);
    }printf("%d",ans);
    return 0;
}

devil.