数列
题目描述
有 n 个元素。第 i 个元素的编号为 i,标识符为 yi,初值 vi=0。序列 y1,…,yn 是 1 至 n 的一个排列。编号和标识符在操作中固定不变。
按顺序执行以下操作。所给区间 [l,r] 均包含两端。
| 操作 |
含义 |
0 l r a b |
对编号在 [l,r] 内的每个元素,将 vi 改为 avi+b |
1 l r a b |
对标识符在 [l,r] 内的每个元素,将 vi 改为 avi+b |
2 l r |
查询编号在 [l,r] 内的元素的数值之和 |
3 l r |
查询标识符在 [l,r] 内的元素的数值之和 |
输入格式
第一行两个整数 n,q,分别表示元素数和操作数。第二行 n 个整数 y1,…,yn。随后 q 行,每行一个操作,格式见上表。
输出格式
按查询顺序,每次输出一行。答案对 536870912 取模,输出范围为 0 至 536870911。
样例 #1
样例输入 #1
4 4
2 1 4 3
0 2 3 4 5
1 1 3 4 7
2 1 1
3 1 1
样例输出 #1
7
27
样例说明
按编号排列,第一次修改后数值是 (0,5,5,0),第二次修改后是 (7,27,5,7)。
数据规模与约定
1≤n,q≤50000,1≤l≤r≤n,0≤a,b≤231−1。