Page 1 of 212

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 .)

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

Page 1 of 212