# HOJ 226: CP (中)

This post was written in Traditional Mandarin Chinese for my fellow competitive programmers in Taiwan.

## Treap

struct Treap {
Treap * lc;
Treap * rc;
unsigned pri;
char val;
int size;
};

int size(Treap * a) { return a ? a->size : 0; }
void pull(Treap * a) {
if (a) a->size = 1 + size(a->lc) + size(a->rc);
}

## 持久化／Copy-On-Write

### 一般來說

Copy-on-write就是你操作一個資料結構的時候，保留舊的東西不要刪掉或改掉。

x = [1,2,3,4,5,6,7,8,9,10]

y = [1,2,42,3,4,5,6,7,8,9,10]

x = (1)→(2)→(3)→(4)→(5)→(6)→(7)→(8)→(9)→(10)
↑
y = (1)→(2)→(42)

### 用到treap上面

a->rc = merge(a->rc, b);
pull(a);
return a;

Treap * aa = new Treap();
aa->lc = a->lc;
aa->rc = merge(a->rc, b);
aa->pri = a->pri;
aa->val = a->val;
pull(aa);
return aa;

## 引用計數

（NPSC那一題不需要這一項優化。）

int refs;

void takeRef(Treap * t) {
if (t) t->refs++;
}
void dropRef(Treap * t) {
if (t) {
t->refs--;
if (t->refs <= 0) {
dropRef(t->lc);
dropRef(t->rc);
delete t;
}
}
}

## Randomized Binary (Search) Tree

### 奇怪的另解

int randomPriority(int size) {
rseed = 0xdefaced * rseed + 1;
unsigned int q = 0xffffffffu / (unsigned int) size;
return r % q;
}

(note: the commenting setup here is experimental and I may not check my comments often; if you want to tell me something instead of the world, email me!)