蒟蒻的自力更生

· · 题解

函数解释：

      unique（）[unique函数的解释](https://www.cnblogs.com/wangkundentisy/p/9033782.html)

      make_pair（a,b)(过于无法理解我自行解释）将a与b压进堆里。a可以用于大根堆的排序

      lower_bound（）[lower_bound函数的解释](https://baike.baidu.com/item/lower_bound/8620039?fr=aladdin)

unique与lower_bound处理完减去数组可以得到处理后的址 （在下面代码有体现）

//方法：如果该容器已满，后来出现的不在容器中的，一定要由容器中的元素中距离下一次出现最远的那个元素来替换掉。 代码挺明确了就直接看吧

#include <bits/stdc++.h>//万能头文件 
using namespace std;//使用命名空间吧ei 
const int INF=0x3fffffff;//定义 
int a[100005],b[100005],last[100005],next[100005],cnt,sum;//定义 
bool vis[100005];//定义 
//用next[i]数组保存第I个内存地址的下一次出现的位置
//last[i]表示 下一次对i的 操作
// vis数组标记当前值是否在堆中
priority_queue <pair<int,int> > h; //建大根堆 
int n,m;//定义 
int main() { //main函数 
    memset(next,1,sizeof(next));//初始化 
    scanf("%d%d",&n,&m);//输入 
    for(int i=1; i<=n; i++) {//循环
        scanf("%d",a+i);//输入 
        b[i]=a[i];//赋值 
    }//结束循环 
    sort(b+1,b+1+n);//排序 
    int num=unique(b+1,b+1+n)-b-1;//去重,离散化，从后往前建出每块主存的操作顺序，返回最右址 
    for(int i=1; i<=n; i++)  {//循环
        a[i]=lower_bound(b+1,b+1+num,a[i])-b;//寻找第一个>=a[i]的数，返回址 
        next[last[a[i]]]=i;//构建 next数组 
        last[a[i]]=i;//构建last数组 
    }//结束循环 
    for(int i=1; i<=n; i++) { //循环 
        while(!h.empty()&&!vis[h.top().second]) h.pop();//如果大根堆不是空的并且堆顶元素的a[i]不在Cache缓存里就删除堆顶元素 
        if(vis[a[i]]) h.push(make_pair(next[i],a[i]));//如果a[i]在Cache缓存里就push进当前点的next[i]值 
        else{//如果a[i]不在Cache里 
            cnt++;//答案++ 
            vis[a[i]]=1;//a[i]标记 
            if(!h.empty()&&sum>=m) {//如果大根堆不是空的并且缓存没有剩余;
                vis[h.top().second]=0;//将堆顶元素的a[i]标记 
                h.pop();//删除堆顶元素 
            }//结束判断 
            if(sum<m) //如果Cache容量有剩余 
                sum++;//缓存++ 
            h.push(make_pair(next[i],a[i]));//把当前点push进去 
        }//结束否则 
    }//结束 循环 
    printf("%d",cnt); //输出答案 
    return 0; //功德圆满 
}//结束main函数

言简意赅