← 返回题目
题库练习 [BJOI2018] 链上二次求和
← 上一题 下一题 →

A7020 | [BJOI2018] 链上二次求和

来源省选 / 2018
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

有一条长度为 $n$ 的链（ $\forall 1 \leq 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$ 的路径是同一条，不要重复计算。

输入格式

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

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

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

输出格式

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

输入输出样例

输入 #1
5 5
1 1 1 1 1
2 5 5
2 1 2
1 1 2 2
2 1 1
1 1 5 3
输出 #1
5
13
9
C++ 编辑器
输入
输出