题目

【模板】线段树 2

题目描述

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

• 将某区间每一个数乘上 $x$

• 将某区间每一个数加上 $x$

• 求出某区间每一个数的和

输入格式

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

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

接下来 $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

样例输入 #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

提示

【数据范围】

对于 $30\%$ 的数据：$n \le 8$，$m \le 10$
对于 $70\%$ 的数据：$n \le 10^3$，$m \le 10^4$
对于 $100\%$ 的数据：$n \le 10^5$，$m \le 10^5$

除样例外，$p = 571373$

（数据已经过加强^_^）

样例说明：

故输出应为 $17$、$2$（ $40 \bmod 38 = 2$ ）

---

我的答案

#include<bits/stdc++.h>
using namespace std;
//时间复杂度log n;
const int maxn=10000005+5;
int p;
long long sum[maxn*4];//节点一段中的和 
struct Tag{//标记要进行几次改变 
	long long cheng;
	long long jia;
};
Tag tag[maxn*2];//叶子节点不需要标签 ，以为叶子节点是父节点的两倍 
Tag fuhe(Tag a,Tag b){//把乘法加法混在一起算 
	return {a.cheng*b.cheng%p,(a.jia*b.cheng+b.jia)%p};//返回给tag 
}
void apply(Tag t,int x,int l,int r){//t作用在x所对应的那一段每个数上 ，先乘t再每个加t 
	sum[x]=(sum[x]*t.cheng+t.jia*(r-l+1))%p;//改变子节点 
	if(l!=r){
		tag[x]=fuhe(tag[x],t);//留下给右孩子树用，24行 
	}
}
void push (int x,int l,int r){//把x上的修改标记推送到孩子身上 
	int mid=(l+r)/2;
	apply(tag[x],x*2,l,mid);
	apply(tag[x],x*2+1,mid+1,r);
	tag[x]={1,0};//修改 重置 
}
void pull(int x,int l,int r){
	//更新sum[x],pull
	sum[x]=(sum[2*x]+sum[2*x+1])%p;
}
long long query(int x,int l,int r,int ql,int qr){
//查询 [ql,qr]和[l,r]相交那一部分之和,
	if(ql>r||qr<l){//保证有相交 
		return 0;
	}
	if(ql<=l&&r<=qr){// 
		return sum[x];
	}
	// 	
	push(x,l,r);
	int mid=(l+r)/2;
	//[l,mid],[mid+1,r]
	return (query(x*2,l,mid,ql,qr)+query(x*2+1,mid+1,r,ql,qr))%p;

}
void modify(int x,int l,int r,int ql,int qr,Tag t){
	if(ql>r||qr<l){//保证相相交 
		return;
	}
	if(ql<=l&&r<=qr){//完全包含 
//		sum[x]+=(r-l+1)*k;
		apply(t,x,l,r);
		return;//易错 
	}
	push(x,l,r);//
	int mid=(l+r)/2;
	modify(x*2,l,mid,ql,qr,t);
	modify(x*2+1,mid+1,r,ql,qr,t);
	//更新sum[x],pull
	pull(x,l,r);
	
}
int a[maxn];
//构建线段树 
void build(int x,int l,int r){//从叶子递归 
	if(l==r){
		sum[x]=a[l];
		return;
	}
	tag[x]={1,0};//tag初始值 
	int mid=(l+r)/2; 
	build(x*2,l,mid);
	build(x*2+1,mid+1,r);
	pull(x,l,r);//求父节点 
}
int main(){
//	ios::sync_with_stdio(0);//加快cin,cout
//	cin.tie(0);
	int n,m;
	cin>>n>>m>>p;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,1,n);
	while(m--){
		int op,l,r,k;
		cin>>op>>l>>k;
		if(op==1){
			cin>>k;
			modify(1,1,n,l,r,{k,0});
		}else if(op==2){
			cin>>k;
			modify(1,1,n,l,r,{k,0});
		}else{
			cout<<query(1,1,n,l,r)<<endl;
		}
	}
	return 0;
}
//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