解題區/解題區 - Zerojudge

a761. 罐頭的記憶體

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 線段樹
    2. 4.2. 分塊離線
    3. 4.3. 分塊在線

Problem

模擬作業系統的 dynamic memory allocation，

  • 宣告連續一段記憶體配置給某個程序，並且標記辨識碼。
  • 若宣告失敗，則輸出碰撞區域中，辨識碼最小的數字。
  • 詢問記憶體存取時，是否合法，若合法輸出程序的辨識碼。

Sample Input

1
2
3
4
5
6
7
8
7
load 29
map 1 25 39
map 2 23 24
map 3 22 25
map 4 25 40
store 33   
store 22

Sample Output

1
2
3
4
5
6
7
fail to load from 29
region 1 created
region 2 created
fail to create region 3, overlap with region 1
fail to create region 4, overlap with region 1
store region to 1
fail to store to 22

Solution

溫馨提示：此題的測資隨機，單純離散化套用二分查找，編號最小使用線性搜索即可通過。by 蔡神 asas

儘管直觀作法可以通過，來討論看看別種作法吧。

  • 線段樹 + 延遲標記 + 離線處理
    離散結果最多有 $O(N + Q)$ 的離散點，單筆操作複雜度為 $O(\log Q)$，空間複雜度 $O(Q)$，空間消耗量相較於其他算法最多 (附加延遲標記的使用)。
  • 分塊算法 + 離線處理
    利用分塊 Unrolled Linked List 的快取優勢來降複雜度，空間複雜度仍然是 $O(Q)$，單筆操作複雜度為 $O(\sqrt{Q})$。空間複雜度的常數比線段樹少一半以上，別忘詢問離線是共同的空間成本。
  • 分塊在線
    直接宣告 $O(2^{32})$ 進行配置，因此分塊大小為 $O(\sqrt{2^{32}})$。將配置連續區段用區間 $[l, r, pid]$ 的方式儲存在塊之中，用一個平衡樹維護每一個塊的狀態。由於要輸出編號最小的，詢問複雜度至少為 $O(65536)$，為了加速詢問可以利用剪枝 (塊的最小值仍大於當前的答案) 來完成。空間複雜度跟實際情況有關，這一做法在當前數據中是最快，記憶體最小的一種辦法，因為在線很多詢問點是沒必要實際存在的。

由於這一題沒有釋放記憶體操作，從均攤上可以清楚，分塊離線的修改離散點的次數最多為 $O(Q)$，也就是每一個點均被塗色僅僅一次，剩下就是在詢問上加速。

線段樹

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1<<21, INF = 0x3f3f3f3f;
class SegmentTree {
public:
    struct Node {
        int val, del;
        void init(int a = 0, int b = 0) {
            val = a, del = b;
        }
    } nodes[MAXN];
    void pushDown(int k, int l, int r) {
        if (nodes[k].del != INF) {
            nodes[k<<1].val = min(nodes[k<<1].val, nodes[k].del);
            nodes[k<<1].del = min(nodes[k<<1].del, nodes[k].del);
            nodes[k<<1|1].val = min(nodes[k<<1|1].val, nodes[k].del);
            nodes[k<<1|1].del = min(nodes[k<<1|1].del, nodes[k].del);
            nodes[k].del = INF;
        }
    }
    void pushUp(int k, int l, int r) {
        nodes[k].val = min(nodes[k<<1].val, nodes[k<<1|1].val);
    }
    void build(int k, int l, int r) { 
        nodes[k].init(INF, INF);
        if (l == r)	return ;
        int mid = (l + r)/2;
        build(k<<1, l, mid);
        build(k<<1|1, mid+1, r);
        pushUp(k, l, r);
    } 
    void assignUpdate(int k, int l, int r, int val) {
        nodes[k].del = min(nodes[k].del, val);
        nodes[k].val = min(nodes[k].val, val);
    }
    void assign(int k, int l, int r, int x, int y, int val) {
        if (x <= l && r <= y) {
            assignUpdate(k, l, r, val);
            return;
        }
        pushDown(k, l, r);
        int mid = (l + r)/2;
        if (x <= mid)	assign(k<<1, l, mid, x, y, val);
        if (y > mid)	assign(k<<1|1, mid+1, r, x, y, val);
        pushUp(k, l, r);
    }
    int query(int k, int l, int r, int x) {
        if (x <= l && r <= x || nodes[k].val == INF)
            return nodes[k].val;
        pushDown(k, l, r);
        int mid = (l + r)/2, ret;
        if (x <= mid)	ret = query(k<<1, l, mid, x);
        else			ret = query(k<<1|1, mid+1, r, x);
        pushUp(k, l, r);
        return ret;
    }
    int query(int k, int l, int r, int x, int y) {
        if (x <= l && r <= y || nodes[k].val == INF)
            return nodes[k].val;
        pushDown(k, l, r);
        int mid = (l + r)/2, ret = INF;
        if (x <= mid)
            ret = min(ret, query(k<<1, l, mid, x, y));
        if (y > mid)
            ret = min(ret, query(k<<1|1, mid+1, r, x, y));
        pushUp(k, l, r);
        return ret;
    }
} tree;
const int MAXQ = 524288;
char cmd[MAXQ][8];
int args[MAXQ][3];
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        map<int, int> R;
        for (int i = 0; i < N; i++) {
            scanf("%s", &cmd[i]);
            int a, b, c;
            if (cmd[i][0] == 'l')
                scanf("%d", &a), R[a] = 0;
            else if (cmd[i][0] == 'm')
                scanf("%d %d %d", &a, &b, &c), R[b] = R[c] = 0;
            else
                scanf("%d", &a), R[a] = 0;
            args[i][0] = a, args[i][1] = b, args[i][2] = c;
        }
        
        int size = 0;
        for (auto &x : R)
            x.second = ++size;
        tree.build(1, 1, size);
        for (int i = 0; i < N; i++) {
            int a, b, c, t;
            a = args[i][0], b = args[i][1], c = args[i][2];
            if (cmd[i][0] == 'l') {
                t = tree.query(1, 1, size, R[a]);
                if (t == INF)
                    printf("fail to load from %d\n", a);
                else
                    printf("load from region %d\n", t);
            } else if (cmd[i][0] == 'm') {
                t = tree.query(1, 1, size, R[b], R[c]);
                if (t != INF)
                    printf("fail to create region %d, overlap with region %d\n", a, t);
                else
                    printf("region %d created\n", a), tree.assign(1, 1, size, R[b], R[c], a);
            } else {
                t = tree.query(1, 1, size, R[a]);
                if (t == INF)
                    printf("fail to store to %d\n", a);
                else
                    printf("store to region %d\n", t);
            }
        }
    }
    return 0;
}

分塊離線

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAXQ = 524288;
class Unrolled {
public:
    int PILE, mask, shift;
    vector< vector<int> > nodes;
    vector<int> dirty;
    void alloc(int size) {
        nodes.clear(), dirty.clear();
        for (PILE = 1, shift = 0; PILE * PILE < size; PILE <<= 1, shift++);
        mask = PILE - 1;
        for (int l = 0, r; l < size; l = r+1) {
            r = min(l+PILE-1, size-1);
            nodes.push_back(vector<int>(r-l+1, INF));
            dirty.push_back(INF);
        }
    }
    int operator[](const int x) const {
        return nodes[x>>shift][x&mask];
    }
    int empty(int l, int r) {
        int bl = l>>shift, br = r>>shift;
        int ret = INF;
        if (bl == br) {
            for (int i = l; i <= r; i++)
                ret = min(ret, (*this)[i]);
            return ret;
        }
        for (int i = bl+1; i < br; i++)
            ret = min(ret, dirty[i]);
        for (int i = (bl+1) * PILE-1; i >= l; i--)
            ret = min(ret, (*this)[i]);
        for (int i = (br) * PILE; i <= r; i++)
            ret = min(ret, (*this)[i]);
        return ret;
    }
    void fill(int l, int r, int val) {
        int bl = l>>shift, br = r>>shift;
        for (int i = bl; i <= br; i++)
            dirty[i] = min(dirty[i], val);
        for (int i = l, bi; i <= r; i++)
            nodes[i>>shift][i&mask] = val;
    }
} mem;
char cmd[MAXQ][8];
int args[MAXQ][3];
int main() {
    int N;
    while (scanf("%d", &N) == 1) {
        map<int, int> R;
        for (int i = 0; i < N; i++) {
            scanf("%s", &cmd[i]);
            int a, b, c;
            if (cmd[i][0] == 'l')
                scanf("%d", &a), R[a] = 0;
            else if (cmd[i][0] == 'm')
                scanf("%d %d %d", &a, &b, &c), R[b] = R[c] = 0;
            else
                scanf("%d", &a), R[a] = 0;
            args[i][0] = a, args[i][1] = b, args[i][2] = c;
        }
        
        int size = 0;
        for (auto &x : R)
            x.second = size++;
        mem.alloc(size);
        for (int i = 0; i < N; i++) {
            int a, b, c, t;
            a = args[i][0], b = args[i][1], c = args[i][2];
            if (cmd[i][0] == 'l') {
                t = mem[R[a]];
                if (t == INF)
                    printf("fail to load from %d\n", a);
                else
                    printf("load from region %d\n", t);
            } else if (cmd[i][0] == 'm') {
                t = mem.empty(R[b], R[c]);
                if (t != INF)
                    printf("fail to create region %d, overlap with region %d\n", a, t);
                else
                    printf("region %d created\n", a), mem.fill(R[b], R[c], a);
            } else {
                t = mem[R[a]];
                if (t == INF)
                    printf("fail to store to %d\n", a);
                else
                    printf("store to region %d\n", t);
            }
        }
    }
    return 0;
}

分塊在線

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
class Unrolled {
public:
    struct Interval {
        long long l, r;
        int pid;
        Interval(long long a = 0, long long b = 0, int c = 0):
            l(a), r(b), pid(c) {}
        bool operator<(const Interval &x) const {
            return l < x.l || (l == x.l && r > x.r);
        }
        bool include(int x) const {
            return l <= x && x <= r;
        } 
    };
    long long PILE, mask;
    int shift;
    vector< set<Interval> > nodes;
    vector<int> dirty;
    void alloc(long long size) {
        nodes.clear(), dirty.clear();
        for (PILE = 1, shift = 0; PILE * PILE < size; PILE <<= 1, shift++);
        mask = PILE - 1;
        for (long long l = 0, r; l < size; l = r+1) {
            r = min(l+PILE-1, size-1);
            nodes.push_back(set<Interval>());
            dirty.push_back(INF);
        }
    }
    int operator[](const long long x) const {
        const set<Interval> &s = nodes[x>>shift];
        auto it = s.upper_bound(Interval(x, x));
        it = it == s.begin() ? it : --it;
        return it == s.end() || !(it->include(x)) ? INF : it->pid;
    }
    int empty(long long l, long long r) {
        int bl = l>>shift, br = r>>shift;
        int ret = INF;
        if (bl == br) {
            set<Interval> &s = nodes[bl];
            auto st = s.upper_bound(Interval(l, l));
            st = st == s.begin() ? st : --st;
            for (auto it = st; it != s.end(); it++) {
                if (max(l, it->l) <= min(r, it->r))
                    ret = min(ret, it->pid);
                if (it->l > r)
                    break;
            }
            return ret;
        }
        for (int i = bl+1; i < br; i++)
            ret = min(ret, dirty[i]);
        for (auto it = nodes[bl].rbegin(); it != nodes[bl].rend() && ret > dirty[bl]; it++) {
            if (max(l, it->l) <= min(r, it->r)) {
                ret = min(ret, it->pid);
            } else {
                break;
            }
        }
        for (auto it = nodes[br].begin(); it != nodes[br].end() && ret > dirty[br]; it++) {
            if (max(l, it->l) <= min(r, it->r)) {
                ret = min(ret, it->pid);
            } else {
                break;
            }
        }
        return ret;
    }
    void fill(long long l, long long r, int val) {
        int bl = l>>shift, br = r>>shift;
        for (int i = bl; i <= br; i++)
            dirty[i] = min(dirty[i], val);
        if (bl == br) {
            nodes[bl].insert(Interval(l, r, val));
            return ;
        }
        for (int i = bl+1; i < br; i++)
            nodes[i].insert(Interval(i*PILE, (i+1)*PILE-1, val));
        nodes[bl].insert(Interval(l, (bl+1) * PILE-1, val));
        nodes[br].insert(Interval(br*PILE, r, val));
    }
} mem;
int main() {
    int N;
    char cmd[8];
    while (scanf("%d", &N) == 1) {
        mem.alloc(1LL<<31);
        for (int i = 0; i < N; i++) {
            scanf("%s", &cmd);
            int a, b, c, t;
            if (cmd[0] == 'l') {
                scanf("%d", &a);
                t = mem[a];
                if (t == INF)
                    printf("fail to load from %d\n", a);
                else
                    printf("load from region %d\n", t);
            } else if (cmd[0] == 'm') {
                scanf("%d %d %d", &a, &b, &c);
                t = mem.empty(b, c);
                if (t != INF)
                    printf("fail to create region %d, overlap with region %d\n", a, t);
                else
                    printf("region %d created\n", a), mem.fill(b, c, a);
            } else {
                scanf("%d", &a);
                t = mem[a];
                if (t == INF)
                    printf("fail to store to %d\n", a);
                else
                    printf("store to region %d\n", t);
            }
        }
    }
    return 0;
}