#P5039. [Jsoi2014]序列维护

    ID: 4137 传统题 2000ms 256MiB 尝试: 539 已通过: 258 难度: 5 上传者: 标签>难度分类普及+/提高-数据结构懒标记线段树标记复合数论同余的加减乘运算CF1700Round1

[Jsoi2014]序列维护

维护数列

题目描述

给定长度为 NN 的非负整数序列 a1,…,aNa_1,\ldots,a_N,需要支持:

  1. 区间所有数乘以一个值。
  2. 区间所有数加上一个值。
  3. 查询区间所有数之和对 PP 取模的结果。

输入格式

从标准输入读入。第一行两个正整数 N,PN,P。

第二行 NN 个非负整数 a1,…,aNa_1,\ldots,a_N。

第三行一个整数 MM,表示操作数。接下来 MM 行,每行为以下格式之一:

  • 1 t g c:把所有 t≤i≤gt\le i\le g 的 aia_i 乘以 cc。
  • 2 t g c:把所有 t≤i≤gt\le i\le g 的 aia_i 加上 cc。
  • 3 t g:查询 ∑i=tgai\sum_{i=t}^g a_i 对 PP 取模的结果。

输出格式

每个类型3操作向标准输出写出一行答案。

样例输入

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

样例输出

2
35
8

样例说明

初始数列为 (1,2,3,4,5,6,7)(1,2,3,4,5,6,7)。第一次乘法后为 (1,10,15,20,25,6,7)(1,10,15,20,25,6,7),第二次操作查询得到 45 mod 43=245\bmod43=2。

第三次操作后为 (1,10,24,29,34,15,16)(1,10,24,29,34,15,16)。最后两次查询分别为 35 mod 43=3535\bmod43=35 和 94 mod 43=894\bmod43=8。

数据范围

1≤N,M≤1051\le N,M\le10^5,1≤P,c≤2×1091\le P,c\le2\times10^9,0≤ai≤2×1090\le a_i\le2\times10^9,1≤t≤g≤N1\le t\le g\le N。