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;
}