题目描述
Mayuri 有 n 颗星星,每颗星星都有一个明亮度 Ai 。Mayuri 时常想知道一个区间 [l,r] 内所有星星的明亮度的总和是多少。但是星星是会眨眼的,所以星星的明亮度是会变化的。有的时候,下标为 y,y+x,y+2x,y+3x,…,y+kx 的星星的明亮度会增加 z。保证 y≤x。
Mayuri 不怎么会数学,请回答她的询问。答案要对 109+7 取模。
输入格式
第一行两个整数 n 和 m,分别表示星星的数量和操作的数量。
接下来一行 n 个数字 Ai,表示初始的明亮度。
接下来 m 行,每行先是一个整数表示操作类型,如果为 1 则是修改操作,接下来 3 个整数 x,y,z;如果是 2 则为询问操作,接下来两个整数 l,r。
输出格式
对于每个询问操作,输出一行表示答案。
样例 #1
样例输入 #1
5 6 1 2 3 4 5 2 2 4 1 1 1 1 2 2 4 2 1 3 1 2 1 2 2 1 3
样例输出 #1
9 12 9 13
提示
Idea:yanQval,Solution:yanQval,Code:yanQval,Data:yanQval&nzhtl1477
对于 10% 的数据,满足 n,m≤1000。
对于另外 10% 的数据,满足 x>1000。
对于另外 10% 的数据,满足 x>300。
对于另外 10% 的数据,满足 n,m≤105。
对于 100% 的数据,1≤n,m≤2×105,1≤y≤x≤n,1≤l≤r≤n,0≤Ai,z≤109+7。