线段树模板(区间乘)luogu3373((基础功能较全)附加单点加乘查！)_线段树区间乘,单点加

题目描述

如题，已知一个数列，你需要进行下面三种操作：

将某区间每一个数乘上 x

将某区间每一个数加上 x

求出某区间每一个数的和

输入格式
第一行包含三个整数 n,m,p，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 n 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。

接下来 m 行每行包含若干个整数，表示一个操作，具体如下：

操作 1： 格式：1 x y k 含义：将区间 [x,y] 内每个数乘上 k

操作 2： 格式：2 x y k 含义：将区间 [x,y] 内每个数加上 k

操作 3： 格式：3 x y 含义：输出区间 [x,y] 内每个数的和对 p 取模所得的结果

输出格式
输出包含若干行整数，即为所有操作 3 的结果。

输入输出样例
输入 #1复制
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
输出 #1复制
17
2
说明/提示
【数据范围】
对于 100% 的数据:n≤100000,m≤100000.

核心

本模板需要先明白先乘后加原则(废话，小学生都知道 )，
然后再打标记时一定带上乘法（加法标记前!），最后不开
longlong见祖宗QAQ(本蒟蒻因这个卡了整整600秒).
(注意：单点修改有时不进行pushdown()会出错！)

代码

#include<bits/stdc++.h>
#define int long long
#define N 200005
#define in read()
using namespace std;

int a[N],n,m,mod;
struct{
int l,r,val,add,mul;}tree[4*N];

inline int in{
	int i=0,f=1;char ch;
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){i=(i<<3)+(i<<1)+(ch^48);ch=getchar();}
	return i*f;
}//神奇快读

inline void pushup(int k)//合并至父区间
{
	tree[k].val=(tree[k<<1].val+tree[k<<1|1].val)%mod;
}

inline void pushdown(int k)//打标记
{
	int add=tree[k].add,mul=tree[k].mul;
	tree[k].add=0,tree[k].mul=1;
	tree[k<<1].val=(tree[k<<1].val*mul)%mod;//乘法在前
	tree[k<<1|1].val=(tree[k<<1|1].val*mul)%mod;
tree[k<<1].val=(tree[k<<1].val+(tree[k<<1].r-tree[k<<1].l+1)*add%mod)%mod;
tree[k<<1|1].val=(tree[k<<1|1].val+(tree[k<<1|1].r-	tree[k<<1|1].l+1)*add%mod)%mod;
	tree[k<<1].mul=(tree[k<<1].mul*mul)%mod;
	tree[k<<1|1].mul=(tree[k<<1|1].mul*mul)%mod;
	tree[k<<1].add=(tree[k<<1].add*mul)%mod;
	tree[k<<1|1].add=(tree[k<<1|1].add*mul)%mod;
	tree[k<<1].add=(tree[k<<1].add+add)%mod;
	tree[k<<1|1].add=(tree[k<<1|1].add+add)%mod;
	return;
}

inline void Build(int k,int l,int r)//建树
{
	tree[k].l=l,tree[k].r=r,tree[k].mul=1;
	if(l==r)
	{
		tree[k].val=a[l]%mod;
		return;
	}
	int m=(l+r)>>1;
	Build(k<<1,l,m);
	Build(k<<1|1,m+1,r);
	pushup(k);
	return;
} 

inline void mul(int k,int l,int r,int v)//区间乘(case1)
{
	if(tree[k].l>=l&&tree[k].r<=r)
	{
		tree[k].val=(tree[k].val*v)%mod;
		tree[k].add=(tree[k].add*v)%mod;
		tree[k].mul=(tree[k].mul*v)%mod;
		return;
	}
	pushdown(k);
	int m=(tree[k].l+tree[k].r)>>1;
	if(m>=l)mul(k<<1,l,r,v);
	if(m+1<=r)mul(k<<1|1,l,r,v);
	pushup(k);
	return;
}

inline void add(int k,int l,int r,int v)//区间加(case2)
{
	if(tree[k].l>=l&&tree[k].r<=r)
	{
		tree[k].val=(tree[k].val+(tree[k].r-tree[k].l+1)*v%mod)%mod;
		tree[k].add=(tree[k].add+v)%mod;
		return;
	}
	pushdown(k);
	int m=(tree[k].r+tree[k].l)>>1;
	if(l<=m)add(k<<1,l,r,v);
	if(m+1<=r)add(k<<1|1,l,r,v);
	pushup(k);
	return;
}

//inline void mulx(int k,int x,int l,int r,int v)//单点乘(caes4)
//{
//	if(l==r)
//	{
//		a[x]=(a[x]*v)%mod;
//		tree[k].val=(tree[k].val*v)%mod;
//		return;
//	}
//	int m=(tree[k].l+tree[k].r)>>1;
//	if(m>=x)mulx(k<<1,x,l,m,v);
//	if(m+1<=x)mulx(k<<1|1,x,m+1,r,v);
//	pushup(k);
//	return;
//}

//inline void addx(int k,int x,int l,int r,int v)//单点加(case5)
//{
//	if(l==r)
//	{
//		a[x]=(a[x]+v)%mod;
//		tree[k].val=(tree[k].val+v)%mod;
//		return;
//	}
//	int m=(tree[k].l+tree[k].r)>>1;
//	if(m>=x)addx(k<<1,x,l,m,v);
//	if(m+1<=x)addx(k<<1|1,x,m+1,r,v);
//	pushup(k);
//	return;
//}

inline int Query(int k,int l,int r)//区间和(case3)
{
	if(tree[k].l>=l&&tree[k].r<=r)return tree[k].val;
	pushdown(k);
	int ans=0;
	int m=(tree[k].l+tree[k].r)>>1;
	if(m>=l)ans=ans+Query(k<<1,l,r)%mod;
	if(m+1<=r)ans=ans+Query(k<<1|1,l,r)%mod;
	return ans%mod;
}

//inline int Queryx(int k,int l,int r,int x)//查单点值(case6)
//{
//	int ans;
//	if(l==r)return tree[k].val;
//	if(tree[k].add)pushdown(k);
//	int m=(tree[k].l+tree[k].r)>>1;
//	if(m>=x)ans=Queryx(k<<1,l,m,x)%mod;
//	if(m+1<=x) ans=Queryx(k<<1|1,m+1,r,x)%mod;
//	return ans%mod;
//}

signed main()
{
	int x,y,z,t;
	n=in,m=in,mod=in;
	for(int i=1;i<=n;i++)
	a[i]=in;
	Build(1,1,n);//建树1-N(需至少四倍于N的空间)
	for(int i=1;i<=m;i++)
	{
		t=in;
		switch(t)//各种操作
		{
			case 1:{
				x=in,y=in,z=in;
				mul(1,x,y,z);	
				break;
			}
			case 2:{
				x=in,y=in,z=in;
				add(1,x,y,z);
				break;
			}
			case 3:{
				x=in,y=in;
				printf("%lld\n",Query(1,x,y));
				break;
			}
//			case 4:{
//				x=in,z=in;
//				mulx(1,x,1,n,z);
//				break;
//			}
//			case 5:{
//				x=in,z=in;
//				addx(1,x,1,n,z);
//				break;
//			}
//			case 6:{
//				x=in;
//				printf("%lld\n",Queryx(1,1,n,x));
//				break;
//			}
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185