#P7983. [JRKSJ R3] practiceZ

    ID: 7007 远端评测题 2000~7000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>2021珂朵莉树,颜色段均摊,ODT洛谷原创O2优化块状链表,块状数组,分块

[JRKSJ R3] practiceZ

题目背景

题目描述

琴琴给了你两个长为 nn 的序列 a,ba,b,请你支持三种操作共 mm 次:

  1. 1 l r x,将 aa 序列的区间 [l,r][l,r] 中的所有数修改为 xx
  2. 2 l r y,将 bb 序列的区间 [l,r][l,r] 中的所有数修改为 yy
  3. 3 l r,求 i=lrj=1biaj\sum_{i=l}^r \sum_{j=1}^{b_i} a_j。答案对 2322^{32} 取模。

输入格式

输入均为整数。

1122 个数 n,mn,m
22nn 个数表示序列 aa
33nn 个数表示序列 bb
接下来 mm 行,每行一个操作,格式见题目描述。

输出格式

对于每个操作 33,一行一个整数表示答案。

4 5
5 5 4 5
3 4 4 1
2 3 3 2
2 2 3 4
3 1 4
1 3 3 2
3 2 4
57
39
5 5
1 7 5 2 5
2 1 5 3 2
1 5 5 3
1 3 5 2
3 1 4
2 1 4 2
3 1 3
33
24
10 10
27 29 12 16 16 6 20 22 17 1
2 6 1 10 4 1 3 10 9 6
2 3 5 6
3 2 10
2 5 10 9
3 5 9
1 1 5 24
1 6 10 12
3 2 3
1 4 6 14
1 4 8 14
3 5 10
956
825
264
924

提示

本题采用捆绑测试。

注:原时间限制为 5s,较为卡常所以被管理改为 7s。

Subtask\text{Subtask} nn\le mm\le 特殊性质 分值 子任务依赖 时间限制
11 500500 10310^3 1010 2s2\text{s}
22 10410^4 11
33 10510^5 3030 1,21,2 4s4\text{s}
44 5×1055\times 10^5 3×1053\times 10^5 数据随机 2020 5s5\text{s}
55 3030 1,2,3,41,2,3,4

对于 100%100\% 的数据,1n5×1051\le n\le 5\times 10^51m3×1051\le m\le 3\times 10^51ai,x1091\le a_i,x\le 10^91bi,yn1\le b_i,y\le n