UVA 11423 - Cache Simulator (树状数组)

题目链接

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

解题思路：因为数据最多有10^7，所以数据访问的序列最长也就是10^7。树状数组的每个位置代表的是访问序列的位置有没有数，因为如果之前的数在后面有访问到的话，那么这个数就应该在后面了，这样前面的那个数就应该不存在。做法：先将要访问的数据序列处理出来，放在队列中，并且找到每个数之前出现过的离它最近的那个位置。查询当前的位置和之前那个出现的位置之间有多少个数（假设dis个）；小于dis的cache的miss++，然后要记得删除树状数组之前的那个位置上的值。如果是没有出现过的数，那么miss肯定是要+1的。注意：每次state都要重新计算miss。

代码：

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
        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
        
          Q; map
         
           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; };