http://codeforces.com/gym/101498/problem/F
對于知道使用情況的置換算法,最優解是找一個最後需要使用的物品替換掉
也就是,如果一個物品後面已經不需要用到,就要拿出來了,礙地方
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiYWan5CM5kTN2ImNxUDO3ITOiBTNzYzXzQzN1ATMwIzLcBTMyIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjLyM3Lc9CX6MHc0RHaiojIsJye.gif)
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 1e5 + 20;
int a[maxn], b[maxn];
int pos[maxn], last[maxn];
typedef pair<int, int> pii;
int tim[maxn], in[maxn], DFN;
struct cmp {
bool operator () (const pii &a, const pii &b) {
if (a.first != b.first) return a.first > b.first;
else return a.second > b.second;
}
};
set< pair<int, int>, cmp> ss;
void work() {
ss.clear();
int n, k;
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", a + i);
b[i] = a[i];
last[i] = n + 1;
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; ++i) {
b[i] = lower_bound(a + 1, a + 1 + n, b[i]) - a;
// printf("%d ", b[i]);
}
// printf("\n");
for (int i = n; i >= 1; --i) {
pos[i] = last[b[i]];
last[b[i]] = i;
}
int fuck = n + 1;
for (int i = 1; i <= n; ++i) {
if (pos[i] == n + 1) pos[i] = fuck++;
}
int ans = 0;
++DFN;
set< pair<int, int> > :: iterator it;
for (int i = 1; i <= n; ++i) {
if (in[b[i]] == DFN) {
ss.erase(make_pair(tim[b[i]], b[i]));
ss.insert(make_pair(pos[i], b[i]));
tim[b[i]] = pos[i];
continue;
}
if (ss.size() == k) {
it = ss.begin();
in[it->second] = DFN - 1;
ss.erase(it);
}
ss.insert(make_pair(pos[i], b[i]));
in[b[i]] = DFN;
tim[b[i]] = pos[i];
ans++;
}
printf("%d\n", ans);
}
int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
int t;
scanf("%d", &t);
while (t--) work();
return 0;
}