#P4303. 数列

    ID: 3519 传统题 1000ms 512MiB 尝试: 410 已通过: 52 难度: 7 上传者: 标签>难度分类提高+/省选-数据结构K-D Tree按维度中位数划分包围盒剪枝标记复合CF2300

数列

数列

题目描述

有 nn 个元素。第 ii 个元素的编号为 ii,标识符为 yiy_i,初值 vi=0v_i=0。序列 y1,…,yny_1,\ldots,y_n 是 11 至 nn 的一个排列。编号和标识符在操作中固定不变。

按顺序执行以下操作。所给区间 [l,r][l,r] 均包含两端。

操作 含义
0 l r a b 对编号在 [l,r][l,r] 内的每个元素,将 viv_i 改为 avi+bav_i+b
1 l r a b 对标识符在 [l,r][l,r] 内的每个元素,将 viv_i 改为 avi+bav_i+b
2 l r 查询编号在 [l,r][l,r] 内的元素的数值之和
3 l r 查询标识符在 [l,r][l,r] 内的元素的数值之和

输入格式

第一行两个整数 n,qn,q,分别表示元素数和操作数。第二行 nn 个整数 y1,…,yny_1,\ldots,y_n。随后 qq 行,每行一个操作,格式见上表。

输出格式

按查询顺序,每次输出一行。答案对 536870912536870912 取模,输出范围为 00 至 536870911536870911。

样例 #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)(0,5,5,0),第二次修改后是 (7,27,5,7)(7,27,5,7)。

数据规模与约定

1≤n,q≤500001\le n,q\le50000,1≤l≤r≤n1\le l\le r\le n,0≤a,b≤231−10\le a,b\le2^{31}-1。