UVA 11423 - Cache Simulator (树状数组)

option=com_onlinejudge&Itemid=8&category=523&page=show_problem&problem=2418" style="">题目链接

题目大意：模仿磁盘缓冲区的工作机制，给你n个不同size的（递增的）磁盘缓冲区。给你要訪问的数据，依据LRU原则，问每一个size的磁盘分别有多少次miss（数据没有在缓存中就是miss）。

解题思路：由于数据最多有10^7，所以数据訪问的序列最长也就是10^7。

树状数组的每一个位置代表的是訪问序列的位置有没有数，由于假设之前的数在后面有訪问到的话，那么这个数就应该在后面了，这样前面的那个数就应该不存在。

做法：先将要訪问的数据序列处理出来，放在队列中，而且找到每一个数之前出现过的离它近期的那个位置。查询当前的位置和之前那个出现的位置之间有多少个数（假设dis个）；小于dis的cache的miss++，然后要记得删除树状数组之前的那个位置上的值。

假设是没有出现过的数，那么miss肯定是要+1的。

注意：每次state都要又一次计算miss。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#include <map>

using namespace std;

const int N = 35;

const int maxn = 1e7 + 5;

#define lowbit(x) ((x)&(-x))

int n;

int Miss[N], Cache[N];

int C[maxn];

char str[N];

void add (int x, int v) {

    while (x < maxn) {

        C[x] += v;

        x += lowbit(x);

    }

}

int sum (int x) {

    int ret = 0;

    while (x > 0) {

        ret += C[x];

        x -= lowbit(x);

    }

    return ret;

}

struct Num {

    int value, pre;

    Num (int value , int pre) {

        this->value = value;

        this->pre = pre;

    }

};

queue<Num> Q;

map<int, int> vis;

void init () {

    int b, y, k;

    memset (Miss, 0, sizeof(Miss));

    vis.clear();

    while (scanf ("%s", str) && str[0] != 'E') {

        if (str[0] == 'R') {

            scanf ("%d%d%d" , &b, &y, &k);

            for (int i = 0; i < k; i++) {

                Q.push(Num(b + y * i, vis[b + y * i]));

                vis[b + y * i] = Q.size();

            }

        } else if (str[0] == 'A') {

            scanf ("%d", &b);

            Q.push(Num (b, vis[b]));

            vis[b] = Q.size();

        } else {

            Q.push(Num (-1, 0));

        }

    }

}

void solve () {

    init();

    memset (C, 0, sizeof (C));

    int cnt = 0;

    while (!Q.empty()) {

        if (Q.front().value >= 0) {

            add(cnt + 1, 1);

            if (Q.front().pre > 0) {

                int dis = sum(cnt + 1) - sum(Q.front().pre);

//                printf ("%d %d %d %d\n", Q.front().value, cnt + 1, Q.front().pre, dis);

                for (int i = 0; i < n; i++) {

                    if (Cache[i] < dis)

                        Miss[i]++;

                    else

                        break;

                }

                add(Q.front().pre, -1);

            } else {

                for (int i = 0; i < n; i++)

                    Miss[i]++;

            }

        } else {

            for (int i = 0; i < n - 1; i++)

                printf ("%d ", Miss[i]);

            printf ("%d\n", Miss[n - 1]);

            memset (Miss, 0, sizeof (Miss));

        }

        Q.pop();

        cnt++;

    }

}

int main () {

    scanf ("%d", &n);

    for (int i = 0; i < n; i++)

        scanf("%d", &Cache[i]);    

    solve();

    return 0;

};