#O1096. 区间乘加与区间和

区间乘加与区间和

题目描述

给定长度为 nn 的序列 aa,维护 qq 次操作:

  • 1 l r v:区间 [l,r][l,r] 每个数加上 vv;
  • 2 l r v:区间 [l,r][l,r] 每个数乘上 vv;
  • 3 l r:询问区间 [l,r][l,r] 的和。

所有运算与答案均对 109+710^9+7 取模。

输入格式

第一行两个整数 n,qn,q。

第二行 nn 个整数 aia_i。

接下来 qq 行,每行一个操作,格式如上。

输出格式

对每个 3 操作输出一行一个整数,表示区间和模 109+710^9+7。

样例 #1

样例输入 #1

5 5
1 2 3 4 5
1 1 3 10
2 1 5 2
3 1 5
1 2 2 100
3 2 2

样例输出 #1

90
124

数据规模与约定

数据范围 说明
1≤n,q≤2×1051 \le n,q \le 2\times10^5 序列长度与操作数
0≤ai,v≤10000 \le a_i,v \le 1000 初始值与操作数
  • 先乘后加:sum = sum*mul + add*len,标记也要按这个顺序更新。
  • 时限较紧,请使用 O((n+q)log⁡n)O((n+q)\log n) 的线段树。