1 /************************************************************** 2     Problem: 1528 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:716 ms 7     Memory:13304 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <queue>12 #include <utility>13  14 using namespace std;15 const int N = 500005;16  17 int n, k, p, ans;18 int a[N], next[N], last[N];19 bool v[N];20 priority_queue <pair <int, int> > h;21  22 int main() {23     int i;24     scanf("%d%d%d", &n, &k, &p);25     for (i = 1; i <= n; ++i)26         last[i] = p + 1;27     for (i = 1; i <= p; ++i)28         scanf("%d", a + i);29     for (i = p; i; --i) {30         next[i] = last[a[i]];31         last[a[i]] = i;32     }33     for (i = 1; i <= p; ++i) {34         if (v[a[i]])35             h.push(make_pair(next[i], a[i])); else36         if (k) {37             h.push(make_pair(next[i], a[i]));38             v[a[i]] = 1, --k, ++ans;39         } else {40             while (!v[h.top().second]) h.pop();41             v[h.top().second] = 0, h.pop();42             h.push(make_pair(next[i], a[i]));43             v[a[i]] = 1, ++ans;44         }45     }46     printf("%d\n", ans);47     return 0;48 }