problem

维护一棵 N 个结点的无根树.

支持两种操作:

  1. 在路径(u, v) 上的每个点上放一个可爱值为 kfafa.
  2. 问所有可爱值在 [l, r] 内的 fafa 到点 p 的距离之和.

solution1


  • 考虑\sum \text{dis} 显然可以转化为 \sum \text{dep(lca)}.

那么这样一来, 我们就考虑如何求\sum \text{dep(lca)}.

先来引入2道题

[Lnoi2014] Lca


  • \sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]

考虑树链剖分, 如果我们对于(u,v), 希望知道\text{dep[lca(u,v)]}.

那么只要在v\to root的路径上给点权+1.

询问u\to root的路径上的点权和就好了.

故, 此题离线做法就一个树链剖分就好了.

复杂度: O(n\log^2n)

Lct可以做到O(n\log n)的复杂度.

[Cf446C] DZY Loves Fibonacci Numbers


支持两个操作:

  1. [l,r]的每一个位置i加上fib[i-l+1]
  2. 区间询问和.

fib定义为斐波那契数列

fib[1]=1, fib[2]=1

这里有一些关于斐波那契数列的性质:

定义类斐波那契数列为第一、二项不一定为1, 但满足a_n=a_{n-1}+a_{n-2}的数列.

下面的a, b,c都是类斐波那契数列

F为斐波那契数列.

  • c_n=a_n+b_na_n满足a_n=a_{n-1}+a_{n-2}, 同理于b

    那么c_n=c_{n-1}+c_{n-2}.

    Proof:

  • a_n = F_{n-2}a_1+F_{n-1}a_2

    为了方便递推, 令F_0=0, F_{-1} = 1.

    Proof: 考虑数学归纳法.

  • \sum_{i=1}^n a_i = a_{n + 2} – a_2

    Proof:

    \begin{aligned} 2\sum_{i=1}^n a_i &=2a_1+2a_2+\dots+2a_n\\ &=a_1 + (a_1+a_2)+\dots+(a_{n-1}+a_n)+a_n\\ &=a_1+a_3+a_4+\dots+a_{n+1}+a_n\\ &=a_1+a_3+a_4+\dots+a_n+a_{n+2}\\ \end{aligned}

    然后左右移项即可.

考虑线段树.

在线段树上的每个节点维护f_1,f_2表示类斐波那契的递推开始2项.

然后下放与询问都可以做到O(1)的了.

总复杂度: O(n\log n)

My code

大大的分割线

回到此题.

根据前2题的启示, 很自然想到树套树先维护fafa权值.

接着在第二颗树中就只要维护支持链加等差数列操作的线段树即可.

而区间加等差数列与加fib数列类似.

维护线段树上每个节点的首项与公差.

下方标记的时候就相当于是将一个等差数列(即三角形)分成两半.

前一半就是个三角形

后一半就是个梯形(长方形+三角形).

故再维护一个区间加标记即可.

题目没有强制在线, 那么可以离线做.

即不用维护一个树链剖分森林, 只要一颗一颗处理过来就好了.

这样可以节省空间.

复杂度: O(n\log^2n)

solution2


  • 考虑所有修改操作在询问前的情况.

这非常好做, 是一个可持久化树链剖分可以做到的事情.

这样一来, 对于原问题考虑对操作按时间分块.

并且一个块操作完后就定期重构.

并不是很会, 所以详细记录一下

设按时间分成了O(x)个块.

  1. 对于块内的询问, 暴力枚举同个时间块的修改操作.

    单个修改分类讨论可以做到O(1).

    这样一次复杂度是O(\frac{n}{x})

    故, 这一步复杂度为O(\frac n x \cdot n)

  2. 对于不是同一块的操作, 考虑之间的联系.

    由于贡献作用在之后的块, 且都会作用上去

    可以先建立起关于它的可持久化树链剖分结构.

    然后暴力扫之后的询问即可.

    这一步复杂度为O(x\cdot n\log n)

然后均值不等式一下就可以使复杂度变为O(\sqrt {n^3\log n}=n^{1.5}\sqrt{\log n})

以上的两种做法我都没有实现, 逃