解題區/解題區 - Zerojudge

b405. 記憶中的序列

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. Test Code
    2. 4.2. Test Generator

Problem

給一個序列，支持插入元素、刪除元素、反轉區間、區間極值、區間總和、區間修改以及最重要的 版本回溯 。

題目輸入會拿上一個答案進行 XOR 的加密，

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
10
9 81 28 6 40 68 74 50 82 62 
15
1 1 83
2 11
3 7 8
4 4 10 28
5 2 6
85 82 89
14 13 13
56 61
57 57 40
58 61
59 61 63
60 57 59 4
61 58 49
137 139 136
37 38 42

decrypt input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
10
9 81 28 6 40 68 74 50 82 62
15
1 1 83
2 11
3 7 8
4 4 10 28
5 2 6
6 1 10
7 4 4
0 5
1 1 16
2 5
3 5 7
4 1 3 60
5 2 9
6 4 7
7 4 8

Sample Output

1
2
3
4
5
6
83
9
56
143
34
381

Solution

持久化 treap，區間反轉，區間最大值，區間最小值，區間總和，插入元素，刪除元素，操作回溯。

這坑爹的題目描述擺明就是拖人下水，只好含淚地寫下去。持久化類型的題目應該是告一段落，就差一個 LCP + HASH 的維護了吧。麻煩的地方在於持久化的懶操作標記傳遞時都要新增加一個節點，這項舉動導致記憶體量非常多，1 秒處理的資訊吃掉 512 MB。二分記憶體上限，終於找到內存池的最多元素個數，中間不小心把多項資訊的 int 型態宣告成 long long，導致內存池一直不夠大。

如果不考慮回溯操作，速度上沒有比暴力算法來得快上很多，treap 基於隨機數的調整，而且每一次修改元素都要增加很多記憶體來補，導致速度上無法領先太多。但如果用暴力法，會造成版本回溯問題，空間會到 $O(
n^2)$，不允許的狀態，持久化造就的平均空間使用$O(Q log N \times sizeof(Node))$，看起來仍然是很巨大的。

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
#include <bits/stdc++.h>
using namespace std;
#define MAXN 7100000
#define MAXQ 60005
class PersistentTreap {
public:
    struct Node;
    static Node *null;
    struct Node {
        Node *lson, *rson;
        int key, size;
        long long val, mnval, mxval, sumval;
        long long adel; // delivery
        int rdel;
        
        Node(long long c = 0, int s = 1): size(s) {
            lson = rson = null;
            key = rand();
            val = mnval = mxval = sumval = c;
            adel = rdel = 0;
        }
        void update() {
            size = 1;
            size += lson->size + rson->size;
        }
        void pushUp() {
            mnval = mxval = sumval = val;
            if (lson != null) {
                mnval = min(mnval, lson->mnval + lson->adel);
                mxval = max(mxval, lson->mxval + lson->adel);
                sumval += lson->sumval + lson->adel * lson->size;
            }
            if (rson != null) {
                mnval = min(mnval, rson->mnval + rson->adel);
                mxval = max(mxval, rson->mxval + rson->adel);
                sumval += rson->sumval + rson->adel * rson->size;
            }
        }
        void pushDown(PersistentTreap &treap) {
            if (adel) {
                val += adel, mnval += adel, mxval += adel;
                if (lson != null) {
                	lson = treap.cloneNode(lson);
                    lson->adel += adel;
                }
                if (rson != null) {
                	rson = treap.cloneNode(rson);
                    rson->adel += adel;
                }
                adel = 0;
            }
            if (rdel&1) {
                if (lson == null)
                    lson = rson, rson = null;
                else if (rson == null)
                    rson = lson, lson = null;
                else
                    swap(lson, rson);
                
                if (lson != null) {
                	lson = treap.cloneNode(lson);
                    lson->rdel += rdel;
                } 
                if (rson != null) {
                    rson = treap.cloneNode(rson);
                    rson->rdel += rdel;
                }
                rdel = 0;
            }
            pushUp();
        }
    } nodes[MAXN], *root[MAXQ];
    int bufIdx, verIdx;
    
    Node* merge(Node* a, Node* b) {
        if (a == null)	return cloneNode(b);
        if (b == null)	return cloneNode(a);
        if (a != null)	a->pushDown(*this);
    	if (b != null)	b->pushDown(*this);
        Node *ret;
        if (a->key < b->key) {
            ret = cloneNode(a);
            ret->rson = merge(a->rson, b);
        } else {
            ret = cloneNode(b);
            ret->lson = merge(a, b->lson);
        }
        ret->update();
        ret->pushUp();
        return ret;
    }
    void split(Node* a, Node* &l, Node* &r, int n) {
        if (n == 0) {
            l = null, r = cloneNode(a);
            return ;
        } 
        if (a->size <= n) {
            l = cloneNode(a), r = null;
            return ;
        }         
        if (a != null)
            a->pushDown(*this);
        if (a->lson->size >= n) {
            r = cloneNode(a);
            split(a->lson, l, r->lson, n);
            r->update();
            r->pushUp();
        } else {
            l = cloneNode(a);
            split(a->rson, l->rson, r, n - (a->lson->size) - 1);
            l->update();
            l->pushUp();
        }
    }
    
    void insert(Node* &a, Node *ver, int pos, long long s[], int sn) {
        Node *p, *q, *r;
        int n = sn;
        split(ver, p, q, pos);
        build(r, 0, n - 1, s);
        p = merge(p, r);
        a = merge(p, q);
    }
    void erase(Node* &a, Node *ver, int pos, int n) {
        Node *p, *q, *r;
        split(ver, p, q, pos - 1);
        split(q, q, r, n);
        a = merge(p, r);
    }
    void reverse(Node* &a, Node *ver, int left, int right) {
        Node *p, *q, *r;
        split(ver, p, q, left - 1);
        split(q, q, r, right - left + 1);
        q->rdel++;
        a = merge(p, q);
        a = merge(a, r);
    }
    void add(Node* &a, Node *ver, int left, int right, long long val) {
        Node *p, *q, *r;
        split(ver, p, q, left - 1);
        split(q, q, r, right - left + 1);
        q->adel += val;
        a = merge(p, q);
        a = merge(a, r);
    }
    long long q_sum, q_max, q_min;
    void q_dfs(Node *u, int left, int right) {
        left = max(left, 1);
        right = min(right, u->size);
        if (left > right)
            return;        
        if (u != null)
            u->pushDown(*this);
        int lsz = u->lson != null ? u->lson->size : 0;
        int rsz = u->rson != null ? u->rson->size : 0;
        if (left == 1 && right == lsz + rsz + 1) {
            q_sum += u->sumval;
            q_max = max(q_max, u->mxval);
            q_min = min(q_min, u->mnval);
            return ;
        }
        if (left <= lsz+1 && lsz+1 <= right) {
            q_sum += u->val;
            q_max = max(q_max, u->val);
            q_min = min(q_min, u->val);
        }
        
        if (u->lson != null && left <= lsz)
            q_dfs(u->lson, left, right);
        if (u->rson != null && right > lsz+1)
            q_dfs(u->rson, left - lsz - 1, right - lsz - 1);
    }
    void q_init() {
        q_max = LONG_LONG_MIN;
        q_min = LONG_LONG_MAX;
        q_sum = 0;
    }
    long long findMax(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_max;
    }
    long long findMin(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_min;
    }
    long long findSum(Node *ver, int left, int right) {
        q_init();
        q_dfs(ver, left, right);
        return q_sum;
    }
    void print(Node *ver) {
        if (ver == null)	return;
        ver->pushDown(*this);
        print(ver->lson);
        printf("[%3lld]", ver->val);
        print(ver->rson);
    }
    void init() {
        bufIdx = verIdx = 0;
        root[verIdx] = null;
    }
private:
    Node* cloneNode(Node* u) {
        Node *ret;
        if (u == null) {
            return u;
        } else {
        	if (bufIdx >= MAXN)
        		exit(0);
            assert(bufIdx < MAXN);
            ret = &nodes[bufIdx++];
            *ret = *u;
            return ret;
        }
    }
    void build(Node* &a, int l, int r, long long s[]) {
        if (l > r)	return ;
        int m = (l + r) /2;
        Node u = Node(s[m]), *p = &u, *q;
        a = cloneNode(p), p = null, q = null;
        build(p, l, m-1, s);
        build(q, m+1, r, s);
        p = merge(p, a);
        a = merge(p, q);
        a->update();
        a->pushUp();
    }
} tree;
PersistentTreap::Node t(0, 0);
PersistentTreap::Node *PersistentTreap::null = &t;
int main() {
    int N, Q;
    long long A[65536];
    long long cmd, x, y, v;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++)
            scanf("%lld", &A[i]);
        tree.init();
        tree.insert(tree.root[0], tree.null, 0, A+1, N);
        scanf("%d", &Q);
        int verIdx = 0;
        long long encrypt = 0, ret = 0;
        for (int i = 1; i <= Q; i++) {
            scanf("%lld", &cmd);
            cmd ^= encrypt;
            if (cmd == 1) { 		// insert
                scanf("%lld %lld", &x, &v);
                x ^= encrypt, v ^= encrypt;
                long long B[] = {v};
                tree.insert(tree.root[i], tree.root[verIdx], (int) x, B, 1);
                verIdx = i;
            } else if (cmd == 2) { 	// erase
                scanf("%lld", &x);
                x ^= encrypt;
                tree.erase(tree.root[i], tree.root[verIdx], (int) x, 1);
                verIdx = i;
            } else if (cmd == 3) { 	// reverse
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                tree.reverse(tree.root[i], tree.root[verIdx], (int) x, (int) y);
                verIdx = i;
            } else if (cmd == 4) { 	// [x, y] += v
                scanf("%lld %lld %lld", &x, &y, &v);
                x ^= encrypt, y ^= encrypt, v ^= encrypt;
                tree.add(tree.root[i], tree.root[verIdx], (int) x, (int) y, v);
                verIdx = i;
            } else if (cmd == 5) {  // max(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                ret = tree.findMax(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 6) {  // min(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt;
                ret = tree.findMin(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 7) {  // sum(A[x:y])
                scanf("%lld %lld", &x, &y);
                x ^= encrypt, y ^= encrypt; 
                ret = tree.findSum(tree.root[verIdx], (int) x, (int) y);
                printf("%lld\n", ret);
                encrypt = ret;
                tree.root[i] = tree.root[verIdx];
                verIdx = i;
            } else if (cmd == 0) {  // back Day x-th
                scanf("%lld", &x);
                x ^= encrypt;
                tree.root[i] = tree.root[x];
                verIdx = i;
            } else {
                puts("WTF");
                return 0;
            }
        }
    }
    return 0;
}

Test Code

暴力法驗證用，不支持加密的輸入運行，用一個 vector 完成。

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
#include <bits/stdc++.h>
using namespace std;
#define MAXN (1<<19)
#define MAXQ 65536
int main() {
    int N, Q;
    long long A[65536];
    long long cmd, x, y, v;
    while (scanf("%d", &N) == 1) {
        for (int i = 1; i <= N; i++)
            scanf("%lld", &A[i]);
        vector< vector<long long> > L;
        L.push_back(vector<long long>(A+1, A+1+N));
        scanf("%d", &Q);
        int verIdx = 0;
        long long encrypt = 0, ret = 0;
        for (int i = 1; i <= Q; i++) {
            scanf("%lld", &cmd);
            vector<long long> TA = L[verIdx];
            if (cmd == 1) {         // insert
                scanf("%lld %lld", &x, &v);
                TA.insert(TA.begin()+x, v);
            } else if (cmd == 2) {  // erase
                scanf("%lld", &x);
                TA.erase(TA.begin()+x-1);
            } else if (cmd == 3) {  // reverse
                scanf("%lld %lld", &x, &y);
                reverse(TA.begin()+x-1, TA.begin()+y);
            } else if (cmd == 4) {  // [x, y] += v
                scanf("%lld %lld %lld", &x, &y, &v);
                for (int i = (int) x-1; i < y; i++)
                    TA[i] += v;
            } else if (cmd == 5) {  // max(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = LONG_LONG_MIN;
                for (int i = (int) x-1; i < y; i++)
                    ret = max(ret, TA[i]);
                printf("%lld\n", ret);
            } else if (cmd == 6) {  // min(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = LONG_LONG_MAX;
                for (int i = (int) x-1; i < y; i++)
                    ret = min(ret, TA[i]);
                printf("%lld\n", ret);
            } else if (cmd == 7) {  // sum(A[x:y])
                scanf("%lld %lld", &x, &y);
                long long ret = 0;
                for (int i = (int) x-1; i < y; i++)
                    ret += TA[i];
                printf("%lld\n", ret);
            } else if (cmd == 0) {  // back Day x-th
                scanf("%lld", &x);
                TA = L[x];
            } else {
                puts("WTF");
                return 0;
            }
            L.push_back(TA), verIdx = i;
            printf("version %d\n", i);
            for (auto &x: TA)
                printf("[%3lld]", x);
            puts("");
        }
    }
    return 0;
}

Test Generator

小測資檢驗用

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <set>
using namespace std;
int main() {
     srand (time(NULL));
    int testcase, n, m, x, y;
    int A[100];
    testcase = 1;
    freopen("in.txt", "w+t", stdout);
//    printf("%d\n", testcase);
    while (testcase--) {
        n = 32;
        printf("%d\n", n);
        for (int i = 0; i < n; i++) {
            printf("%d%c", rand(), i == n-1 ? '\n' : ' ');
        }
        m = 1000;
        printf("%d\n", m);
        vector<int> L;
        L.push_back(n);
        for (int i = 1; i <= m; i++) {
            while (true) {
                int cmd = rand()%8;
                if (n == 1 && cmd == 2)
                    continue;
                if (cmd == 0) {
                	int x = rand()%i;
                	printf("%d %d\n", cmd, x);
                	n = L[x];
                }
                if (cmd == 1)
                    printf("%d %d %d\n", cmd, rand()%(n+1), rand()), n++;
                if (cmd == 2)
                    printf("%d %d\n", cmd, rand()%n+1), n--;
                if (cmd == 3) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d\n", cmd, x, y);
                }
                if (cmd == 4) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d %d\n", cmd, x, y, rand());
                }
                if (cmd == 5 || cmd == 6 || cmd == 7) {
                    x = rand()%n+1, y = rand()%n+1;
                    if (x > y)  swap(x, y);
                    printf("%d %d %d\n", cmd, x, y);
                }
                break;
            }
            L.push_back(n);
        }
    }
    return 0;
}