#P4105. [thoi2015]平方运算

    ID: 3312 传统题 4000ms 512MiB 尝试: 573 已通过: 156 难度: 8 上传者: 标签>CF2400提高+/省选-功能图入度剥离最小公倍数懒标记线段树势能分析鸣谢佚名上传

[thoi2015]平方运算

题目描述

现有一个长度为 nn 的序列 {X1,X2,…,Xn}\{X_1,X_2,\dots,X_n\},要求支持两种操作:

  1. 0 l r\texttt{0 l r}:对于 i∈[l,r]i \in [l,r],Xi←Xi2mod  pX_i \gets X_i^2 \mod p。
  2. 1 l r\texttt{1 l r}:询问 ∑i=lrXi\sum_{i=l}^r X_i。

输入格式

第一行有三个整数 n,m,pn,m,p,分别代表序列的长度、平方操作与询问操作的总次数以及在平方操作中所要模的数。

接下来一行 nn 个数代表一开始的序列 {X1,X2,…,Xn}\{X_1,X_2,\dots,X_n\}。

接下来 mm 行,每行三个整数 op,l,rop,l,r。其中 opop 代表本次操作的类型。若 op=0op=0,代表这是一次平方操作,平方的区间为 [l,r][l,r];如果 op=1op=1,代表这是一次询问操作,询问的区间为 [l,r][l,r]。

输出格式

对于每次的询问操作,输出一行代表这段区间内数的总和。

注意:答案没有对任何数取模。

3 3 11
1 2 3
1 1 3
0 1 3
1 1 3
6
14

提示

对于 100%100\% 的数据,Xi∈[0,p), l,r∈[1,n]X_i \in [0,p),~l,r \in [1,n].

n,m,pn,m,p 的范围如下:

测试点编号 nn mm pp
1 10001000 233233
2 23322332
3 100000100000 55
4 81928192
5 2323
6 4545
7 3737
8 5500055000 41854185
9 58505850
10 29752975
11 25422542
12 20152015
13 6000060000 20032003
14 6500065000 20102010
15 7000070000 45934593
16 7500075000 45624562
17 8000080000 10341034
18 8500085000 58315831
19 9000090000 99059905
20 100000100000 99779977

题目来源

鸣谢佚名上传