Day7-例1

难度级别：B； 运行时间限制：1000ms； 运行空间限制：256000KB； 代码长度限制：2000000B

试题描述

 

在计算机中，CPU只能和高速缓存Cache直接交换数据。当所需的内存单元不在Cache中时，则需要从主存里把数据调入Cache。此时，如果Cache容量已满，则必须先从中删除一个。 例如，当前Cache容量为3，且已经有编号为10和20的主存单元。 此时，CPU访问编号为10的主存单元，Cache命中。 接着，CPU访问编号为21的主存单元，那么只需将该主存单元移入Cache中，造成一次缺失（Cache Miss）。 接着，CPU访问编号为31的主存单元，则必须从Cache中换出一块，才能将编号为31的主存单元移入Cache，假设我们移出了编号为10的主存单元。 接着，CPU再次访问编号为10的主存单元，则又引起了一次缺失。我们看到，如果在上一次删除时，删除其他的单元，则可以避免本次访问的缺失。 在现代计算机中，往往采用LRU(最近最少使用)的算法来进行Cache调度——可是，从上一个例子就能看出，这并不是最优的算法。 对于一个固定容量的空Cache和连续的若干主存访问请求，聪聪想知道如何在每次Cache缺失时换出正确的主存单元，以达到最少的Cache缺失次数。

输入

输入文件第一行包含两个整数N和M(1<=M<=N<=100,000)，分别代表了主存访问的次数和Cache的容量。 第二行包含了N个空格分开的正整数，按访问请求先后顺序给出了每个主存块的编号(不超过1,000,000,000)。

输出

输出一行，为Cache缺失次数的最小值。 

输入示例

6 2

1 2 3 1 2 3

输出示例

4

题解：有一个"很显然"的结论：窝萌要删集合中下一次出现时间尽量靠后的元素是极好的= =，于是弄个堆维护一下就行。。。还有个小技巧：讨论时的第一种情况只要添加就可以了，因为next明显是递增的，以后不会访问到原先的点，也就不用再删除了。

（懒得用set写了treap= =）

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #define PAU putchar(' ') 9 #define ENT putchar('\n')10 #define CH for(int d=0;d<2;d++)if(ch[d])11 using namespace std;12 const int maxn=100000+10,maxnode=200000+10,inf=-1u>>1;13 struct data{ int nxt,p;}x[maxn];14 bool operator<(const data&a,const data&b){ return a.nxt
            
             Q;int next[maxn],A[maxn];16 inline int read(){17 int x=0,sig=1;char ch=getchar();18 for(;!isdigit(ch);ch=getchar())if(ch=='-')sig=0;19 for(;isdigit(ch);ch=getchar())x=10*x+ch-'0';20 return sig?x:-x;21 }22 inline void write(int x){23 if(x==0){putchar('0');return;}if(x<0)putchar('-'),x=-x;24 int len=0,buf[15];while(x)buf[len++]=x%10,x/=10;25 for(int i=len-1;i>=0;i--)putchar(buf[i]+'0');return;26 }27 struct node{28 node*ch[2];int r,siz,v;29 void init(){r=rand();siz=1;ch[0]=ch[1]=NULL;}30 void update(){siz=1;CH{siz+=ch[d]->siz;}return;}31 }treap[maxnode],*nodecnt=treap,*root;queue
             
              R;32 node*neawnode(){node*k;if(R.empty())k=nodecnt++;else k=R.front(),R.pop();k->init();return k;}33 void del(node*&x){R.push(x);x=NULL;return;}34 void rotate(node*&x,int d){35 node*k=x->ch[d^1];x->ch[d^1]=k->ch[d];k->ch[d]=x;x->update();k->update();x=k;return;36 }37 void insert(node*&x,int v){38 if(!x)x=nodecnt++,x->init(),x->v=v;39 else{ int d=v>x->v;insert(x->ch[d],v);40 if(x->r
              
               ch[d]->r)rotate(x,d^1);else x->update();41 }return;42 }43 void remove(node*&x,int v){44 if(x->v==v){45 if(x->ch[0]&&x->ch[1]){46 int d=x->ch[0]->r>x->ch[1]->r;47 rotate(x,d);remove(x->ch[d],v);48 }else{node*k;x=x->ch[0]?x->ch[0]:x->ch[1];del(k);}49 }else remove(x->ch[v>x->v],v);50 if(x)x->update();return;51 }52 void print(node*x){53 if(!x)return;print(x->ch[0]);printf("%d ",x->v);print(x->ch[1]);return;54 }55 bool num(node*x,int v){56 if(!x)return false;57 if(x->v==v)return true;58 if(v>x->v)return num(x->ch[1],v);59 else return num(x->ch[0],v);60 }61 int n,m,b[maxn];62 int main(){63 int tp;64 n=read();m=read();65 for(int i=1;i<=n;i++){x[i].nxt=read();x[i].p=i;}66 sort(x+1,x+n+1);int cur=0;67 for(int i=1;i<=n;i++){68 if((i==1)||(x[i].nxt!=x[i-1].nxt))cur++;A[x[i].p]=cur;69 }70 for(int i=n;i;i--){71 if(b[A[i]]==0)next[i]=n+1;72 else next[i]=b[A[i]];73 b[A[i]]=i;74 }int ans=0;75 for(int i=1;i<=n;i++){76 if(root&&num(root,A[i]))Q.push((data){next[i],A[i]});77 else if(!root||root->siz