某島

… : "…アッカリ~ン . .. . " .. .
October 31, 2012

SGU 550. Tree Queries Online

Brief description:

。。。給定一棵 N 階邊權樹,每次選擇一條邊拆開,輸出當前邊的權值。。。記作 w。。
。。並將拆開的兩顆子樹中,較小的一顆子樹上的邊全部 × w,較大子樹的邊全部 + w。。。
。。( N <= 2e5, 強制在線。。)。。

Analysis:

… 前回 Southern Subregional Programming Contest 2012 的 Problem I。。
。。。。。。比賽時第一反應 dsu 倒著搞。。讀到強制在線以後就 SB 了。。。。。 Euler Tour Tree 確實一次都沒有寫過。。(雖然就在前一天還在吃飯的時候和 二妹 討論來著。。。
。。所以賽後就膜拜了一下 CLJ 的代碼。。。發現這種非完全形態的 ETT 還是不難搞的。。。(既樹的形態不發生改變。。沒有換根。。

。。歐拉序列的每個位置都是伸展樹的一個結點,難點是甩區間的時候。。。(這裡由於最後都是一些小塊。。而且引用的是區間位置。。也不太好直接在左右加 -oo 和 +oo 哨兵。。
(CLJ 這裡的處理方法。。假設當前子樹是 [a, b], 提取的區間是 [l, r] 。。則分成 [a, l-1] [l, r] [r+1, b] 三塊。。。左右兩塊切出去以後再鏈接上。。。

。。Euler Tour Tree。。。

(..我發現 CLJ 的伸展樹我的 同步率是很高的。。(比如我們都在類裡面搞了一個函數判斷是左孩子還是右孩子。。(我的是 sgn() 。。她的是 dir()。。。。

.. 然後看下面這段。。

void rot(Node*t) {
	Node*p = t->p;
	p->relax();
	t->relax();
	bool d = t->dir();
	p->p->setc(t, p->dir());
	p->setc(t->ch[!d], d);
	t->setc(p, !d);
	p->update();
}

void pushTo(Node*t) {
	static Node*stack[MAX_N * 2];
	int top = 0;
	while (t != null) {
		stack[top++] = t;
		t = t->p;
	}
	for (int i = top - 1; i >= 0; --i) {
		stack[i]->relax();
	}
}

void splay(Node*t, Node*f = null) {
	pushTo(t);
	while (t->p != f) {
		if (t->p->p == f)
			rot(t);
		else
			(t->dir() == t->p->dir()) ? (rot(t->p), rot(t)) : (rot(t), rot(t));
	}
	t->update();
}

(pushTo 疑似是 LCT 裡面的操作。。可刪。。。
。。然後 CLJ 這裡的 rot 和 splay 函數是實現在外部的。。(。原因似乎是默認形參列表裡面要用到哨兵 null。。
。。。。我的處理方法是在內部定義了一個 static node* NIL 。。。(然後在 mian 函數剛開始的時候給她賦值。。。

External link:

http://acm.sgu.ru/problem.php?contest=0&problem=550