2014-10-27

UVa 12538 - Version Controlled IDE

1. Problem
2. Sample Input
3. Sample Output
4. Solution
1. 4.1. 可持久化 Treap
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

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 個節點。

操作定義

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

$$\text{ treap merge(treap a, treap b) } \\ < \text{treap, treap} > \text{ 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()

$\text{ treap merge(treap a, treap b) }$

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

split()

$< \text{treap, treap} > \text{ split(treap a, int n) }$

若$size(left(a)) \le n \\ \left \{ l, r \right \} = split(left(a), n)$ ，並且將 a 的左子樹改成 r。返回結果$\left \{ l, a \right \}$
若$size(left(a)) > n \\ \left \{ l, r \right \} = split(right(a), n - size(left(a)) - 1)$ ，並且將 a 的右子樹改成 l。返回結果$\left \{ a, r \right \}$

另解

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

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

#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
*/

Morris' Blog