「JSOI 2010」缓存交换

题目大意：

每一次删除的元素是下一次出现最晚的那一个。

#include <cstdio>
#include <cstring>
#include <map>
#include <set>

const int N = 100005;

struct Node {
    int x, y;
    bool operator < (const Node &rhs) const {
        return y < rhs.y;
    }
};

int a[N], b[N];

std::set<Node> s;
std::map<int,int> c;

int read() {
    int x = 0; char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}

int main() {
    int n = read(), m = read(), ans = 0;
    memset(b, 0x3f, sizeof b);
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        if (c.count(a[i])) b[c[a[i]]] = i;
        c[a[i]] = i;
    }
    for (int i = 1; i <= n; ++i) {
        if (s.find((Node){a[i], i}) != s.end())
            s.erase((Node){a[i], i}), --ans;
        else if (s.size() == m) s.erase(--s.end());
        s.insert((Node){a[i], b[i]}), ++ans;
    }
    printf("%d\n", ans);
    return 0;
}