[BJOI2018] 链上二次求和

时间限制：4000MS     内存限制：131072KB

难度：\(6.2\)

• 题目描述

YJC 有一棵 \(n\) 个节点的树， \(i\)、\(i+1\) （\(1 \leq i < n\)）节点间有一条边，第 \(i\) 个点的权值为整数 \(a_i\) 。

现在他有 \(m\) 个询问：

操作 \(1\)（修改）：给定树上两个节点 \(u\)、\(v\) 和一个整数 \(d\)，表示将树上 \(u\) 到 \(v\) 唯一的简单路径上每个点权值都加上 \(d\)。

操作 \(2\)（询问）：给定两个正整数 \(l\)、\(r\) ，表示求树上所有节点个数大于等于 \(l\) 且小于等于 \(r\) 的简单路径节点权值和之和。由于答案很大，只用输出对质数 \(1000000007\) 取模的结果即可。

一条节点个数为 \(k\) 的简单路径节点权值和为这条上所有 \(k\) 个节点（包括端点）的权值之和，而本题中要求是对所有满足要求的简单路径，求这一权值和的和。

树边是无向的，所以路径也是无向的，即点 \(1\) 到点 \(2\) 的路径与点 \(2\) 到点 \(1\) 的路径是同一条，不要重复计算。

• 输入格式

输入第一行包含两个正整数 \(n\)、\(m\)，分别表示节点个数和操作次数。

第二行包含 \(n\) 个整数，其中第 \(i\) 个数 \(a_i\) 为第 \(i\) 个点的初始权值。

接下来 \(m\) 行，每行为 1 u v d  或 2 l r  的形式，分别表示进行一次操作 \(1\)（修改）或操作 \(2\)（询问）。

• 输出格式

对于每次询问，输出一行一个整数，表示答案对 \(1000000007\) 取模的余数。

• 样例输入

• 样例输出

• 样例说明

节点个数为 \(5\) 的简单路径只有 \(1\) 条，权值和为 \(5\)，故第一次询问输出 \(5\) 。

节点个数为 \(1\) 的简单路径有 \(5\) 条，每条权值和都是 \(1\)；节点个数为 \(2\) 的简单路径有 \(4\) 条，每条权值和都是 \(2\)，故第二次询问输出 \(13\) 。

在将点 \(1\) 和点 \(2\) 的权值加 \(2\) 后， \(5\) 条节点个数为 \(1\) 的简单路径权值和分别为 \(3\)、\(3\)、\(1\)、\(1\)、\(1\) ，故第三次询问输出 \(9\) 。

• 数据规模与约定

记操作 \(1\)（修改）的次数为 \(m’\)。

对于全部数据， 保证 \(n \leq 200000, m \leq 500000, m’ \leq 100000, 0 \leq a_i < 1000000007\)，

\(1 \leq u \leq n, 1 \leq v \leq n, 0 \leq d < 1000000007, 1 \leq l \leq r \leq n\)。

测试点	\(n \leq\)	\(m \leq\)	\(m’ \leq\)	约束
1	\(50\)			无
2
3	\(300\)
4
5	\(5000\)	\(5000\)	\(5000\)
6		\(5 \times 10^5\)
7
8			\(10^5\)
9	\(2 \times 10^5\)	\(1\)	\(0\)	保证 \(l=1, r=n\)
10		\(5 \times 10^5\)		无
11			\(10^5\)	保证 \(u=v\)
12				保证 \(l=1, r=n\)
13				保证 \(u=1, v=n, a_i=0\)
14				保证 \(u=1, v=n\)
15				保证 \(d=1, a_i=0\)
16				保证 \(d=1\)
17				保证 \(a_i=0\)
18
19				无
20

 

 

加强版：YZOJ P4611 区间加多项式（YJC 的数组/多项式？）

 

---

 

 

标题 = 正解 系列（

询问的这个很奇怪的东西它其实是 \(\displaystyle\sum\limits_{k=l}^r {\sum\limits_{i=k}^n {\sum\limits_{j=i-k+1}^i a_j}}\) 。

好复杂，记 \(A_i = \displaystyle\sum\limits_{j=1}^i a_j\) 即 \(a_i\) 的前缀和，那么变成 \(\displaystyle\sum\limits_{k=l}^r {\sum\limits_{i=k}^n {\left(A_i – A_{i-k}\right)}}\) 。

拆开，变成 \(\displaystyle\sum\limits_{k=l}^r {\sum\limits_{i=k}^n A_i – \sum\limits_{i=0}^{n-k}A_i}\) 。

还是好复杂，再记 \(B_i = \displaystyle\sum\limits_{j=1}^i A_j\) 即 \(A_i\) 的前缀和，那么变成 \(\displaystyle\sum\limits_{k=l}^r {\left(B_n – B_{k-1} – B_{n-k}\right)}\) 。

拆开，变成 \(\displaystyle \left(r-l+1\right)B_n – \sum\limits_{i=l-1}^{r-1} B_i – \sum\limits_{i=n-r}^{n-l} B_i\) 。

于是发现可以用 线段树/树状数组 维护 \(B_i\) ，现在考虑修改如何操作。

在 \(a\) 上区间加常数，变成在 \(A\) 上区间加一次函数，变成在 \(B\) 上区间加二次函数。

可以随便手推一下式子：设 \(\mbox{len}=r-l+1\) ，

对于 \(l \leq i \leq r\)，有 \(B_i \mathrel{+}= \displaystyle\frac{\left(i-l+1\right)\left(i-l+2\right)}{2}d\) ；

对于 \(r < i \leq n\)，有 \(B_i \mathrel{+}= \displaystyle\frac{\mbox{len}\left(\mbox{len}+1\right)}{2}d + \mbox{len}\left(i-r\right)d\) 。

线段树 分别维护各次项系数（标记永久化 \(>\) 打 \(\mbox{tag}\)），区间修改/区间查询 即可。