Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

06/13
13:07
树链剖分 线段树

[bzoj 3626] [LNOI2014]LCA

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

给出一个n个节点的有根树(编号为0到n-1,根节点为0)。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度,LCA(i,j)表示i与j的最近公共祖先。
有q次询问,每次询问给出l r z,求sigma_{l<=i<=r}dep[LCA(i,z)]。
(即,求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和)

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行2个整数n q。
接下来n-1行,分别表示点1到点n-1的父节点编号。
接下来q行,每行3个整数l r z。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

输出q行,每行表示一个询问的答案。每个答案对201314取模输出

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5 2
0
0
1
1
1 4 3
1 4 2

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

8
5

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

共5组数据,n与q的规模分别为10000,20000,30000,40000,50000。

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

对于一组l,r,z,我们可以把从z到根上面的每个点的权值都加+1,然后对于l-r的每个点询问这个点到根的权值和。这样的操作是可以叠加的,可以看成对于l-r的每个点到根的权值都+1,然后查询z到根的权值。于是我们有了一个这样的算法:一次加入0-n-1的每个点,对于一个z答案为work(r)-work(l-1),离线操作就行了。

 

[bzoj 3626] [LNOI2014]LCA