Description

在计算机中, 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 缺失次数.

Input

输入文件第一行包含两个整数 \(n\) 和 \(m\), 分别代表了主存访问的次数和 Cache 的容量.

第二行包含了 \(n\) 个空格分开的正整数, 按访问请求先后顺序给出了每个主存块的编号 (不超过 \(10^9\)) .

Output

输出一行, 为 Cache 缺失次数的最小值.

Sample Input

6 2
1 2 3 1 2 3

Sample Output

4

Data Range

对于所有数据, 满足:\(1 \leq m \leq n \leq 10^5\).

Explanation

最少使用次数可以用数对维护, 整个系统可以用 STL 水过.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <map>

using namespace std;
typedef long long lli;
const int maxn = 100100;

struct cache {
    int x, val;
    cache(int _1, int _2) {
        x = _1, val = _2;
    }
}; bool operator < (cache a, cache b) {
    return a.val < b.val;
}

int n, m;
int arr[maxn], next[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    // Indicing next values
    map<int, int> mp;
    map<int, bool> vis;
    for (int i = n; i >= 1; i--) {
        if (mp.find(arr[i]) != mp.end())
            next[i] = mp[arr[i]];
        else
            next[i] = n + 1;
        mp[arr[i]] = i;
    }
    // Brute force, with optimization
    priority_queue<cache> que;
    int tot = 0, res = 0;
    for (int i = 1; i <= n; i++) {
        if (vis[arr[i]] == true) {
            que.push(cache(arr[i], next[i]));
            continue;
        }
        if (tot == m) {
            tot -= 1;
            while (!que.empty()) {
                cache c = que.top();
                que.pop();
                if (!vis[c.x])
                    continue;
                vis[c.x] = false;
                break;
            }
        }
        res += 1;
        vis[arr[i]] = true;
        que.push(cache(arr[i], next[i]));
        tot += 1;
    }
    // Output
    printf("%d\n", res);
    return 0;
}