P3373 【模板】线段树 2 帮帮蒟蒻吧 QAQ

#include <bits/stdc++.h> 
using namespace std;
int n,m,q;
const int maxn = 1e5 + 1;
int a[maxn] = {};
struct segTree{
	int val,add,mul;
}tree[maxn*4] = {};
void pushDown(int s, int t,int node){
	int left = 2*node, right = 2*node + 1, mid = (s + t)/2;
	int k_add = tree[node].add, k_mul = tree[node].mul; 
	tree[node].add  = 0; tree[node].mul = 1;
	
	tree[left].val = (tree[left].val*k_mul + k_add*(mid-s+1)) % m;
	tree[right].val = (tree[right].val*k_mul + k_add*(t-mid)) % m;
	
	tree[left].add = (tree[left].add*k_mul + k_add) % m;
	tree[right].add = (tree[right].add*k_mul + k_add) % m;
	
	tree[left].mul = (tree[left].mul*k_mul) % m;
	tree[right].mul = (tree[right].mul*k_mul) % m;
}
void buildTree(int s, int t, int node){
	tree[node].mul = 1; tree[node].add = 0;
	int left = 2*node, right = 2*node + 1, mid = (s + t)/2;
	if(s == t){
		tree[node].val = a[t];
		return ;
	}
	buildTree(s,mid,left);
	buildTree(mid+1,t,right);
	tree[node].val = tree[left].val + tree[right].val;
}
void update_mul(int l, int r, int k, int s, int t, int node){
	int left = 2*node, right = 2*node + 1, mid = (s + t)/2;
	if(l <= s && t <= r){
		tree[node].val = (tree[node].val*k) % m;
		tree[node].mul = (tree[node].mul*k) % m;
		tree[node].add = (tree[node].add*k) % m;
		return ;
	}
	pushDown(s, t, node);
	if(l <= mid) update_mul(l,r,k,s,mid,left);
	if(r > mid) update_mul(l,r,k,mid+1,t,right);
	tree[node].val = tree[left].val + tree[right].val;
}
void update_add(int l, int r, int k, int s, int t, int node){
	int left = 2*node, right = 2*node + 1, mid = (s + t)/2;
	if(l <= s && t <= r){
		tree[node].val = (tree[node].val + (t-s+1)*k) % m;
		tree[node].add = (tree[node].add + k) % m;
		return ;
	}
	pushDown(s, t, node);
	if(l <= mid) update_add(l,r,k,s,mid,left);
	if(r > mid) update_add(l,r,k,mid+1,t,right);
	tree[node].val = tree[left].val + tree[right].val;
}
int getsum(int l,int r, int s, int t,int node){
	int left = 2*node, right = 2*node + 1, mid = (s + t)/2;
	if(l <= s && t <= r){
		return tree[node].val;
	}
	pushDown(s, t, node);
	int sum = 0;
	if(l <= mid) sum += getsum(l,r,s,mid,left);
	if(r > mid) sum += getsum(l,r,mid+1,t,right);
	return sum;
}
int main() {
	cin>>n>>q>>m;
	for(int i = 1; i <= n; ++i) cin>>a[i];
    buildTree(1,n,1);
    do{
    	int t,x,y,k;
    	cin>>t;
    	if(t == 1){
    		cin>>x>>y>>k;
    		update_mul(x,y,k,1,n,1);
		}
		if(t == 2){
			cin>>x>>y>>k;
			update_add(x,y,k,1,n,1);
		}
		if(t == 3){
			cin>>x>>y;
			cout<<getsum(x,y,1,n,1)<<'\n';
		}
	}while(--q);
	return 0;
}