UVA 11423 - Cache Simulator(樹狀數組)

UVA 11423 - Cache Simulator

題目鏈接

題意：題目講的大概就是幾個cash，每次操作可以加入一個或一些數據，如果數據之前有就是hit，命中後的數據就不會消失，如果沒有就miss，當容量超過cash容量時，就會把之前最早沒命中的一個丟掉，每次START就執行這些命令，計算miss次數並輸出

思路：由於最多就2^24的數據，所以可以開一個樹狀數組，每個位置表示第i個添加進去的數據，並且把每個數據對應的位置記錄下來，下次如果添加到一個之前有的數據，就利用樹狀數組查詢上一次到這一次之間一共有多少個數據，如果數據超過cash大小，那麼就說明上一次的已經被丟棄，就會多一次miss，然後hit成功後就把上一次的數據位置-1，把這個數據定在當前添加位置+1。注意每次START的時候要重新計算一次

代碼：

#include 
#include 
#include 
using namespace std;

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

const int N = 35;
const int MAXN = (1<<24) + 5;
int n, cach[N], bit[MAXN];

void add(int x, int v) {
    while (x < MAXN) {
	bit[x] += v;
	x += lowbit(x);
    }
}

int get(int x) {
    int ans = 0;
    while (x) {
	ans += bit[x];
	x -= lowbit(x);
    }
    return ans;
}

int get(int l, int r) {
    return get(r) - get(l - 1);
}

char op[10];
int ans[N], vis[MAXN], now;

void init() {
    now = 0;
    memset(bit, 0, sizeof(bit));
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++)
	scanf("%d", &cach[i]);
}

void tra(int num) {
    if (vis[num]) {
	int len = get(vis[num], now);
	for (int i = 0; i < n; i++) {
	    if (cach[i] >= len) break;
	    ans[i]++;
	}
	add(vis[num], -1);
    }
    else {
	for (int i = 0; i < n; i++)
	    ans[i]++;
    }
    add(vis[num] = ++now, 1);
}

void solve() {
    int x, b, y, nn;
    while (scanf("%s", op)) {
	if (op[0] == 'E') break;
	if (op[0] == 'S') {
	    for (int i = 0; i < n; i++)
		printf("%d%c", ans[i], i == n - 1 ? '\n' : ' ');
	    memset(ans, 0, sizeof(ans));
	}
	if (op[0] == 'A') {
	    scanf("%d", &x);
	    tra(x);
	}
	if (op[0] == 'R') {
	    scanf("%d%d%d", &b, &y, &nn);
	    for (int i = 0; i < nn; i++)
		tra(b + y * i);
	}
    }
}

int main() {
    while (~scanf("%d", &n)) {
	init();
	solve();
    }
    return 0;
}