Processing math: 100%
解題區/解題區 - UVa

UVa 12538 - Version Controlled IDE

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution
    1. 4.1. 可持久化 Treap
      1. 4.1.1. 操作定義
      2. 4.1.2. merge()
      3. 4.1.3. split()
    2. 4.2. 另解

Problem

題目有三種字符串的操作：

  • 1 p s: 在當前字串位置 p 後插入 s 字串。
  • 2 p c: 將當前字串位置 p 後面連續 c 個字符移除。
  • 3 v p c: 在版本號 v 的字串中，在位置 p 之後印出 c 個字元。

由於怕離線處理，因此輸入的數值會進行加密，加密的原則－每個數字會增加數值 d，其 d 為當前打印字符 c 的個數。

Sample Input

1
2
3
4
5
6
7
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6

Sample Output

1
2
3
bcdef
bcg
bxyc

Solution

代碼算法詳見 《可持久化數據結構研究》杭州外國語學校－陳立杰　那篇所寫的 Treap(樹堆)。

這題的離線作法是預先紀錄需要的版本號位置，在邊處理的時候隨時保存答案，以免造成記憶體過大儲存。既然他進行了加密，可見我們不能把每一個版本號的字串儲存，這就是其麻煩之處。

接下來說明的作法，是將每個字符當作節點，在一個二元搜尋樹上，利用中序走訪的結果表示一個字串。

可持久化 Treap

Treap 主要概念是平衡樹，也就是儲存有序的結構，支持插入、刪除、查找數字。冠上可持久化平衡樹，就是一個維護歷史版本的平衡樹。

Treap 每一個節點具有 <key, value>，仍然是一個二元搜尋樹，但同時也是一個 heap。單純看 key 呈現一個二元搜尋樹，如果看 value 則會是 heap。key 跟 value 是挺像的，我的代碼誤打了名稱。而 Treap 效率完全取決於隨機決定的 value 值進行平衡調整。

對於可持久化 Treap 而言，是一個具有平衡樹特性，但不需要做任何旋轉操作的樹。每一次將修改操作替代為一個增加節點的方式 ( 用增加替代修改 的精神)，在記憶體耗量就是 O(m log n)，m 是其操作，log n 是樹內結構的期望深度。每一次操作期望只修改 log n 個節點。

操作定義

這裡只會講到可持久化，拆分成兩個操作，而原本的插入、刪除、查找都可以利用這兩個操作完成。

 treap merge(treap a, treap b) <treap, treap> split(treap a, int n) 
  • merge a b : 將兩個 Treap a, b 進行合併成一個 Treap。
  • split a n : 將 Treap a 拆成前 n 小個元素為一個 Treap，剩餘為另一個 Treap。

插入一個元素相當於 split 一次，將兩個部分中間放置一個元素後，依序將其 merge 起來。

刪除一個元素相當於 split 兩次，將中間單一元素的 Treap 忽略，將第一和第三部分的 Treap merge 起來。

merge()

 treap merge(treap a, treap b) 
  • 若 a, b 其中一個是 null treap，回傳另一個非空樹。
  • 若key(a)≤key(b)
    讓 a 的左子樹不變，而 a 的右子樹變成merge(right(a),b) 的 treap 結果。
  • 若key(a)>key(b)
    讓 b 的右子樹不變，而 b 的左子樹變成merge(a,left(b)) 的 treap 結果。

split()

<treap, treap> split(treap a, int n) 
  • 若size(left(a))≤n{l,r}=split(left(a),n) ，並且將 a 的左子樹改成 r。返回結果{l,a}
  • 若size(left(a))>n{l,r}=split(right(a),n−size(left(a))−1) ，並且將 a 的右子樹改成 l。返回結果{a,r}

另解

在 g++ 头文件中，<ext/rope>中有成型的块状链表，在 using namespace __gnu_cxx; 空间中，其操作十分方便。

不用手刻，而且歷史版本的儲存速度也是 O(1)，裡面應該進行了很多記憶體控管。沒有細讀過，但是其支持相當厲害。看到這一篇代碼被不到百行的流程搞定。不過塊狀鏈表的複雜度仍然是O(n1.5)，比起隨機的可持久化 treap 還是慢了些。

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
#include <stdio.h> 
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#define MAXN (1<<23)
#define MAXQ 65536
struct node;
node *null;
struct node {
    node *lson, *rson;
    int key, size;
    char label; // user def label
    
    node(char c = 0, int s = 1):label(c), size(s) {
        lson = rson = null;
        key = rand();
    }
    void update() {
        size = 1;
        size += lson->size + rson->size;	
    }
} nodes[MAXN], *root[MAXQ];
struct treap {
    int bufIdx = 0;
    int prob_c; // this problem need.
    node* getNode(node* u) {
        node *ret;
        if (u == null) {
            return u;
        } else {
            ret = &nodes[bufIdx++];
            *ret = *u;
            return ret;
        }
    }
    node* merge(node* a, node* b) {
        if (a == null)	return getNode(b);
        if (b == null)	return getNode(a);
        node *ret;
        if (a->key < b->key) {
            ret = getNode(a);
            ret->rson = merge(a->rson, b);
        } else {
            ret = getNode(b);
            ret->lson = merge(a, b->lson);
        }
        ret->update();
        return ret;
    }
    void split(node* a, node* &l, node* &r, int n) {
        if (n == 0) {
            l = null, r = getNode(a);
        } else if (a->size <= n) {
            l = getNode(a), r = null;
        } else if (a->lson->size >= n) {
            r = getNode(a);
            split(a->lson, l, r->lson, n);
            r->update();
        } else {
            l = getNode(a);
            split(a->rson, l->rson, r, n - (a->lson->size) - 1);
            l->update();
        }
    }
    void build(node* &a, int l, int r, char s[]) {
        if (l > r)	return ;
        int m = (l + r) /2;
        node u = node(s[m]), *p = &u, *q;
        a = getNode(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();
    }
    void insert(node* &a, node *ver, int pos, char s[]) {
        node *p, *q, *r;
        int n = strlen(s);
        split(ver, p, q, pos);
        build(r, 0, n - 1, s);
        p = merge(p, r);
        a = merge(p, q);
    }
    void remove(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 print(node *ver) {
        if (ver == null)	return;
        print(ver->lson);
        if (ver->label == 'c')	prob_c++; // this problem need
        putchar(ver->label);
        print(ver->rson);
    }
    void printdebug(node *ver) {
        if (ver == null)	return;
        print(ver->lson);
        putchar(ver->label);
        print(ver->rson);
    }
    void traversal(node *ver, int pos, int n) {
        node *p, *q, *r;
        split(ver, p, q, pos - 1);
        split(q, q, r, n);
        print(q);
    }
    void init() {
        bufIdx = 0; 
        prob_c = 0;
        null = &nodes[bufIdx++];
        null->size = 0;
    }
} tree;
int main() {
    int n;
    while (scanf("%d", &n) == 1) {
        tree.init();
        int cmd, v, p, c, verIdx;
        char s[128];
        root[verIdx = 0] = null;
        for (int i = 0; i <= n; i++)
            root[i] = null;
        for (int i = 0; i < n; i++) {
            scanf("%d", &cmd);
            if (cmd == 1) {
                scanf("%d %s", &p, s);
                p -= tree.prob_c;
                tree.insert(root[verIdx + 1], root[verIdx], p, s);
                verIdx++;
            } else if (cmd == 2) {
                scanf("%d %d", &p, &c);
                p -= tree.prob_c, c -= tree.prob_c;
                tree.remove(root[verIdx + 1], root[verIdx], p, c);
                verIdx++;
            } else {
                scanf("%d %d %d", &v, &p, &c);
                v -= tree.prob_c, p -= tree.prob_c, c -= tree.prob_c;
                tree.traversal(root[v], p, c);
                puts("");
            }
        }
    }
    return 0;
}
/*
6
1 0 abcdefgh
2 4 3
3 1 2 5
3 3 3 4
1 4 xy
3 5 4 6
*/