UVa 11423 Cache Simulator

問題

最後からk個のアクセスのメモリをキャッシュするコンピュータがある。
このコンピュータに次のようなクエリが来る。

ADDR x : xの番地にアクセスする。
RANGE b y n : bの番地から、0≦i＜nとしてb + i * yの番地に順にアクセスする。
STAT : 前回のSTATから、現在までのキャッシュミスの回数を表示する。

クエリが一種類と、キャッシュのサイズがN個与えられるので、
キャッシュのサイズそれぞれに対して与えられたクエリを処理したときの、
キャッシュミスの回数をSTATの命令が来たときに、それぞれ表示せよ。

制約条件

N≦30
クエリの個数は20000以下。
メモリアクセスの回数の合計は10^7を超えない。
番地は24bit以下の正の整数。

方針

今メモリの番地xにアクセスするとする。
番地xに前回アクセスしたときの時間をprev[x], 現在の時間をcurとする。

すると、prev[x]からcurまでの時間のうちにアクセスされたメモリの番地の種類の数がキャッシュのサイズ以下ならば、番地xはキャッシュに載っていると言える。

これを上手く数えるにはbinary indexed treeを使えばよい。
時間curに番地xにアクセスしたとき、BITのcurに1を足し、
prev[x]に-1を引くようにする。
すると、（上の更新処理を行う直前に）
BITの1からcurまでの和からBITの1からprev[x]までの和を引いた値が、
時間prev[x]からcurまでにアクセスされたメモリの番地の種類の数になるようになる。

番地は大きいのでもちろん座標圧縮する。

ソースコード

const int MX = 10000010;
int n, sz[30], prev[MX], ans[30];
int a[MX][3], bit[MX], type[MX];
char op[100];

inline void add(int i, int x){
	for(; i < MX; i += i & -i) bit[i] += x;
}
inline int sum(int i){
	int res = 0;
	for(; i; i -= i & -i) res += bit[i];
	return res;
}

int main(){
	scanf("%d", &n);
	rep(i, n) scanf("%d", sz + i);
	
	vector<int> vs;
	int m = 0;
	
	while(scanf("%s", op), op[0] != 'E'){
		if(op[0] == 'R'){
			int b, y, k;
			scanf("%d%d%d", &b, &y, &k);
			a[m][0] = b; a[m][1] = y; a[m][2] = k;
			for(int i = b, j = 0; j < k; j++, i += y) vs.push_back(i);
			m++;
		}
		else if(op[0] == 'A'){
			scanf("%d", a[m]);
			vs.push_back(a[m][0]);
			a[m++][2] = 1;
		}
		else type[m++] = 1;
	}
	
	sort(vs.begin(), vs.end());
	vs.erase(unique(vs.begin(), vs.end()), vs.end());
	
	rep(i, vs.size()) prev[i] = -1;
	int pos = 0;
	
	rep(h, m){
		if(type[h] == 1){
			rep(i, n) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' '), ans[i] = 0;
			continue;
		}
		
		int b = a[h][0], y = a[h][1], k = a[h][2];
		
		for(int i = b, j = 0; j < k; j++, i += y){
			int x = lower_bound(vs.begin(), vs.end(), i) - vs.begin();
			
			if(prev[x] < 0){
				rep(it, n) ans[it]++;
				add(pos + 1, 1);
			}
			else{
				int d = sum(pos + 1) - sum(prev[x]);
				rep(it, n){
					if(d > sz[it]) ans[it]++;
				}
				add(pos + 1, 1);
				add(prev[x] + 1, -1);
			}
			prev[x] = pos++;
		}
	}
}