F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5291. -- [Bjoi2018]链上二次求和

5291: [Bjoi2018]链上二次求和

Time Limit: 140 Sec  Memory Limit: 512 MB
Submit: 128  Solved: 47
[Submit][Status][Discuss]

Description

有一条长度为n的链(1≤i<n,点i与点i+1之间有一条边的无向图),每个点有一个整数权值,第i个点的权值是
a_i。现在有m个操作,每个操作如下:
操作1(修改):给定链上两个节点u、v和一个整数d,表示将链上u到v唯一的简单路径上每个点权值都加上d。
操作2(询问):给定两个正整数L、r,表示求链上所有节点个数大于等于L且小于等于r的简单路径节点权值和之和。
由于答案很大,只用输出对质数1000000007取模的结果即可。
一条节点个数为k的简单路径节点权值和为这条上所有k个节点(包括端点)的权值之和,
而本题中要求是对所有满足要求的简单路径,求这一权值和的和。
由于是无向图,路径也是无向的,即点1到点2的路径与点2到点1的路径是同一条,不要重复计算。

Input

输入第一行包含两个正整数n、m,分别表示节点个数和操作次数。
第二行包含n个整数,其中第ii个数ai为第ii个点的初始权值。
接下来m行,每行为1 u v d或2 l r的形式,分别表示进行一次操作1(修改)或操作2(询问)。
记操作 1(修改)的次数为 m
n <= 200000, 
m <= 500000, 
m'<= 100000, 
0 <= a_i <1000000007
1 <= u <= n
1<= v <= n 
0 <= d < 1000000007
l <= r <= n

Output

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

Sample Input

5 5
1 1 1 1 1
2 5 5
2 1 2
1 1 2 2
2 1 1
1 1 5 3

Sample Output

5
13
9

HINT

Source

鸣谢佚名上传

[Submit][Status][Discuss]

HOME Back