P2318 [HNOI2005] 虚拟内存 题解

前言

这远古题怎么还能交题解。

思路

考虑使用数据结构直接模拟题目操作，这里直接使用线段树。

线段树的下标代表内存空间，每个节点里存两个 int 和一个 pair，两个 int 分别代表当前节点里有几个下标已经有数了，另一个只在叶子节点有用，代表当前节点存储的数是多少；pair 第一维代表访问次数，第二维代表插入时间。同时开一个 map，记录某个数在内存里的下标。

模拟过程如下：

  • 若当前数在 map 里有值，则将线段树上其对应下标处加 11，同时答案加 11，否则继续下一步；

  • 使用线段树上二分找出一个还没有被占用的下标，若能找到这样的下标，则将其修改为当前值，同时更新 map 里的下标，否则继续下一步；

  • 若当前所有下标都被占用，则在线段树上查询访问次数最少、插入时间最早的下标，将该位置之前对应的值在 map 里的下标置为 00，并在线段树上修改为当前值。

细节详见代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
constexpr int N = 1e4+5;

struct node{
    int s,id;
    pii t;
};

int n,q;

struct SGT{
    node tr[N<<2];
    inline void up(int p){
        tr[p].s = tr[p<<1].s+tr[p<<1|1].s;
        tr[p].t = min(tr[p<<1].t,tr[p<<1|1].t);
    }
    void upd(int d,int l,int r,int p,node x){	//修改当前位置的值
        if(d==l && l==r)	tr[p] = x;
        else{
            int mid = (l+r)>>1;
            if(mid>=d)	upd(d,l,mid,p<<1,x);
            else    upd(d,mid+1,r,p<<1|1,x);
            up(p);
        }
    }
    void add(int d,int l,int r,int p,int x){	//访问次数+1
        if(d==l && l==r)	tr[p].t.fst+=x;
        else{
            int mid = (l+r)>>1;
            if(mid>=d)	add(d,l,mid,p<<1,x);
            else    add(d,mid+1,r,p<<1|1,x);
            up(p);
        }
    }
    int _place(int l,int r,int p){	//线段树上二分，找第一个未被访问的下标
        if(l==r)	return l;
        int mid = (l+r)>>1;
        if(tr[p<<1].s<(mid-l+1))	return _place(l,mid,p<<1);
        else    return _place(mid+1,r,p<<1|1);
    }
    int place(){return tr[1].s==n?-1:_place(1,n,1);}
    node qmin(int l,int r,int p){	//如果所有位置都被访问了，就查找访问次数最少、插入时间最早的下标
        if(l==r)	return tr[p];
        int mid = (l+r)>>1;
        return tr[p<<1].t<tr[p<<1|1].t?qmin(l,mid,p<<1):qmin(mid+1,r,p<<1|1);
    }
}sgt;

unordered_map<int,int> pl;

void solve(){
    read(n),read(q);
    int ans = 0;
    for(int i=1;i<=q;i++){
        int x;read(x);
        if(pl[x]){
            ++ans;
            sgt.add(pl[x],1,n,1,1);
        }
        else{
            int p = sgt.place();
            if(p!=-1){
                pl[x] = p;
                sgt.upd(p,1,n,1,{1,x,{0,i}});
            }
            else{
                node now = sgt.qmin(1,n,1);
                sgt.upd(pl[now.id],1,n,1,{1,x,{0,i}});
                pl[x] = pl[now.id],pl[now.id] = 0;
            }
        }
    }	
    cout<<ans;
}