SPOJ 375. Query on a tree

Brief description :

動態維護樹中兩點之間路徑上邊權的最大值。

Tags: Classical

Analysis :

經典問題.. . 樹鏈剖分 300- 行,3.10+ s
動態樹 150- 行。。。 2.90+ s…

(目前 Yang Zhe 作業里的 全局平衡二叉樹 還不知道怎麼實現。>_<。) 樹鏈剖分(。。過去的寫法。。。3s+-。。。
上面是我最開始時的寫法。。寫的非常小心謹慎。。。上來就分別對結點、邊、路徑各定義了一組結構體。。。(Vertex, Edge, Path … 然後全程指針指來指去。。
點和邊各有一個 host 指針。。(點寄宿在邊上。。邊寄宿在重路徑上。。。
。。路徑的本體是一棵線段樹,(。。為了刷榜還特地寫成了自下向上維護的形式。(因為有剪枝。。。。
。然後記錄其最高點的 Vertex 的指針。。(。head。。(。。跳鏈和詢問的時候計算 offset 都要用到。。。
。。

樹鏈剖分(。。。現在的寫法。。3s+-。。。
.. 只保留的 path 這一個結構體。。直接記錄每個點所在的路徑。。。

External link:

https://www.spoj.pl/problems/QTREE/

SPOJ 9392. Play With Sequence

(由於被 fgd BS 了英文。。我把題目背景都刪了。。)

Brief description :

You are given a sequence A[1], A[2],…, A[N]. On this sequence you have to apply M operations: Add all the elements whose value are in range [l, r] by d or, ask for a query how many element are in range [l, r].
( 1≤ N ≤ 250,000, M ≤ 50,000), |A[i]| ≤ 1,000,000,000 .)

ゆっくり読んでください …