YZOJ P4643 [BJOI2018] 链上二次求和

[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}\)),区间修改/区间查询 即可。

 

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注