此文为博主原创题解，转载时请通知博主，并把原文链接放在正文醒目位置。
题目链接：https://www.luogu.org/problem/show?pid=3372
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入样例#1：5 5输出样例#1：
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
11
8
20
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
分析： 板子题。增加了一个sdouble数组作为乘法的lazy标记其实乘法应该用mul slazy初始化为0，sdouble初始化为1. 每次下放标记时要先下放乘法再下放加法，注意乘法标记都是乘上去的，随时取模。 其他的直接看代码就好了（异常丑陋）... 特别提醒：update(o)容易误写成update[o]，一定要注意！！！！！ 这东西害我调了一个下午 AC代码：1 #include<cstdio>
2 #include<algorithm>
3 #include<cmath>
4 #include<cstring>
5 #include<queue>
6
7 const long long MAXN = 100005;
8
9 inline void read(long long &x)
10 {
11 char ch = getchar(),c = ch;x = 0;
12 while(ch < '0' || ch > '9') c = ch,ch = getchar();
13 while(ch >= '0' && ch <= '9') x = (x<<1)+(x<<3)+ch-'0',ch = getchar();
14 if(c == '-') x = -x;
15 }
16
17 long long n,m,op,x,y,k,MOD;
18 long long sdata[MAXN<<2],slazy[MAXN<<2],sdouble[MAXN<<2],num[MAXN];
19
20 inline long long max(long long a,long long b)
21 {return a>b?a:b;}
22
23 void update(long long o)
24 {
25 sdata[o] = (sdata[o<<1]+sdata[o<<1|1]) % MOD;
26 }
27
28 void build(long long l,long long r,long long o)
29 {
30 sdouble[o] = 1;
31 slazy[o] = 0;
32 if(l == r)
33 {
34 sdata[o] = num[l];
35 return;
36 }
37 long long mid = (l+r)>>1;
38 build(l,mid,o<<1);
39 build(mid+1,r,o<<1|1);
40 update(o);
41 }
42
43 inline void putdown(long long l,long long r,long long o)
44 {
45 if(sdouble[o] == 1 && !slazy[o]) return;
46 long long mid = (l+r)>>1;
47 sdata[o<<1] = (sdata[o<<1]*sdouble[o] + (mid-l+1)*slazy[o])%MOD;
48 sdata[o<<1|1] = (sdata[o<<1|1]*sdouble[o] + (r-mid)*slazy[o])%MOD;
49 sdouble[o<<1] = (sdouble[o<<1]*sdouble[o]) % MOD;
50 sdouble[o<<1|1] = (sdouble[o<<1|1]*sdouble[o]) % MOD;
51 slazy[o<<1] = (slazy[o]+slazy[o<<1]*sdouble[o]) % MOD;
52 slazy[o<<1|1] = (slazy[o]+slazy[o<<1|1]*sdouble[o]) % MOD;
53 slazy[o] = 0;
54 sdouble[o] = 1;
55 }
56
57 void modify(long long l,long long r,long long o,long long ll,long long rr,long long k)
58 {
59 if(ll <= l && rr >= r)
60 {
61 slazy[o] = (slazy[o] + k) % MOD;
62 sdata[o] = ((r-l+1)*k + sdata[o]) % MOD;
63 return;
64 }
65 long long mid = (l+r)>>1;
66 putdown(l,r,o);
67 if(ll <= mid) modify(l,mid,o<<1,ll,rr,k);
68 if(rr > mid) modify(mid+1,r,o<<1|1,ll,rr,k);
69 update(o);
70 }
71
72 void change(long long l,long long r,long long o,long long ll,long long rr,long long k)
73 {
74 if(ll <= l && rr >= r)
75 {
76 sdouble[o] = sdouble[o]*k % MOD;
77 slazy[o] = slazy[o]*k % MOD;
78 sdata[o] = sdata[o]*k % MOD;
79 return;
80 }
81 long long mid = (l+r)>>1;
82 putdown(l,r,o);
83 if(ll <= mid) change(l,mid,o<<1,ll,rr,k);
84 if(rr > mid) change(mid+1,r,o<<1|1,ll,rr,k);
85 update(o);
86 }
87
88 long long ask(long long l,long long r,long long o,long long ll,long long rr)
89 {
90 if(ll <= l && rr >= r)
91 return sdata[o];
92 long long mid = (l+r)>>1;
93 long long ans = 0;
94 putdown(l,r,o);
95 if(ll <= mid) ans = (ans + ask(l,mid,o<<1,ll,rr))%MOD;
96 if(rr > mid) ans = (ans + ask(mid+1,r,o<<1|1,ll,rr))%MOD;
97 return ans;
98 }
99
100 int main()
101 {
102 read(n),read(m),read(MOD);
103 for(register int i = 1;i <= n;++ i)
104 read(num[i]);
105 build(1,n,1);
106 for(register int i = 1;i <= m;++ i)
107 {
108 read(op);
109 if(op == 1)
110 {
111 read(x),read(y),read(k);
112 change(1,n,1,x,y,k);
113 }
114 else if(op == 2)
115 {
116 read(x),read(y),read(k);
117 modify(1,n,1,x,y,k);
118 }
119 else
120 {
121 read(x),read(y);
122 printf("%lld\n",ask(1,n,1,x,y)%MOD);
123 }
124 }
125 return 0;
126 }