Heidi and Library (medium)

Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.

Input
Same as the easy version, but the limits have changed: 1 ≤ n, k ≤ 400 000.

Output
Same as the easy version.

Examples

input
4 100
1 2 2 1
output
2

input
4 1
1 2 2 1
output
3

input
4 2
1 2 3 1
output
3

这是A.heidi and library的升级版，
http://blog.csdn.net/wu_tongtong/article/details/72854205
总体思路还是一样，但是需要用堆维护：
每过一天，设当天的书是a[i]，我们就要把下一次出现的a[i]的位置扔进堆（大根堆）里，如果是最后一次出现，就加入元素INF，
在图书馆满了之后，我们找到堆中最大的元素对应的书目扔掉就好了。
要注意的一点是：即使是在图书馆里已经有了这本书，过了这一天也要把ta的后继加入堆中

这里写代码片
#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

const int INF=10000100;
const int N=400010;
int n,k;
struct node{
    int x,nxt;
};
node a[N];
struct node2{
    int x,sum;
};
node2 heap[N*2];
int have[N];
int wz[N],tot=0,ans=0,tt=0;

void swap(node a,node b)
{
    node c;
    c=a;
    a=b;
    b=c;
    return;
}

void add(int x,int bh) //大根堆 
{
    int now=++tt;
    heap[now].x=bh;
    heap[now].sum=x;
    int fa=now>>1;
    while (fa!=0&&heap[now].sum>heap[fa].sum)
    {
        swap(heap[now],heap[fa]);
        now=fa;
        fa=now>>1;
    }
    return; 
}

int get()
{
    int ans=heap[1].x;
    heap[1]=heap[tt];
    tt--;
    int now=1;
    int son=now<<1;
    if (heap[son].sum<heap[son+1].sum) son++;
    while (son<=tt&&heap[now].sum<heap[son].sum)
    {
        swap(heap[now],heap[son]);
        now=son;
        son=now<<1;
        if (heap[son].sum<heap[son+1].sum) son++;
    }
    return ans;
}

void doit()
{
    int i,j;
    for (i=1;i<=n;i++)
    {
        if (have[a[i].x]==0&&tot<k)
        {
            have[a[i].x]=1;
            add(a[i].nxt,i);
            tot++;
            ans++;
        }
        else if (have[a[i].x])
        {
            add(a[i].nxt,i);
            continue;
        }
        else
        {
            int bh=get();
            have[a[bh].x]=0;
            //printf("%d,",a[bh].x);
            have[a[i].x]=1;
            add(a[i].nxt,i);
            ans++;
        }
    }
    printf("%d",ans);
    return;
}

int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i].x);
    for (int i=n;i>=1;i--)
    {
        if (wz[a[i].x]==0) a[i].nxt=INF;
        else a[i].nxt=wz[a[i].x];
        wz[a[i].x]=i;
    }
    doit();
    return 0;
}