线段树板子

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, m, k, x, y, op;
int a[N];
struct node {
	int l, r, size, tot, lazy;
}segmentTree[N << 2];
void build(int left, int right, int node) {
	segmentTree[node].size = right - left + 1, segmentTree[node].l = left, segmentTree[node].r = right;
	if(left == right) {
		segmentTree[node].tot = a[left];
		return;
	}
	int mid = left + ((right - left) >> 1);
	build(left, mid, node << 1);
	build(mid + 1, right, node << 1 | 1);
	segmentTree[node].tot = segmentTree[node << 1].tot + segmentTree[node << 1 | 1].tot;
}
void tag(int node, int val) {
	segmentTree[node].tot += segmentTree[node].size * val;
	segmentTree[node].lazy += val;
}
void push_down(int node) {
	if(segmentTree[node].lazy) {
		tag(node << 1, segmentTree[node].lazy), tag(node << 1 | 1, segmentTree[node].lazy);
		segmentTree[node].lazy = 0;
	}
}
void modify(int left, int right, int val, int node) {
	if(left <= segmentTree[node].l && segmentTree[node].r <= right) {
		tag(node, val);
		return;
	}
	push_down(node);
	int mid = segmentTree[node].l + ((segmentTree[node].r - segmentTree[node].l) >> 1);
	if(left <= mid) modify(left, right, val, node << 1);
	if(right > mid) modify(left, right, val, node << 1 | 1);
	segmentTree[node].tot = segmentTree[node << 1].tot + segmentTree[node << 1 | 1].tot;
}
int query(int left, int right, int node) {
	if(left <= segmentTree[node].l && segmentTree[node].r <= right) {
		return segmentTree[node].tot;
	}
	push_down(node);
	int mid = segmentTree[node].l + ((segmentTree[node].r - segmentTree[node].l) >> 1);
	if(left <= mid && right > mid) return query(left, right, node << 1) + query(left, right, node << 1 | 1);
	else if(left <= mid) return query(left, right, node << 1);
	else return query(left, right, node << 1 | 1);
}
signed main() {
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	build(1, n, 1);
	while(m--) {
		scanf("%lld%lld%lld", &op, &x, &y);
		if(op == 1) {
			scanf("%lld", &k); 
			modify(x, y, k, 1);
		} else {
			printf("%lld\n", query(x, y, 1));
		}
	}
	return 0;
}

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N = 1e5 + 5;
int n, m, p, x, y, k, op;
int a[N];
struct node{
	int left, right, size, sum, lazy_muti, lazy_add;
} segementTree[N << 2];
void update(int index) {
	segementTree[index].sum = (segementTree[index << 1].sum + segementTree[index << 1 | 1].sum) % p;
}
void tag(int index, int lazy_muti, int lazy_add) {
	segementTree[index].sum = (segementTree[index].sum * lazy_muti + segementTree[index].size * lazy_add) % p;
	segementTree[index].lazy_muti = (segementTree[index].lazy_muti * lazy_muti) % p;
	segementTree[index].lazy_add = (segementTree[index].lazy_add * lazy_muti + lazy_add) % p;
}
void push_down(int index) {
	if(segementTree[index].lazy_muti != 1 || segementTree[index].lazy_add) {
		tag(index << 1, segementTree[index].lazy_muti, segementTree[index].lazy_add);
		tag(index << 1 | 1, segementTree[index].lazy_muti, segementTree[index].lazy_add);
		segementTree[index].lazy_muti = 1;
		segementTree[index].lazy_add = 0;
	}
}
void build(int index, int left, int right) {
	segementTree[index] = {left, right, right - left + 1, 0, 1, 0};
	if(left == right) {
		segementTree[index].sum = a[left];
		return;
	}
	int mid = left + ((right - left) >> 1);
	build(index << 1, left, mid);
	build(index << 1 | 1, mid + 1, right);
	update(index);
}
void muti(int index, int left, int right, int val) {
	if(left <= segementTree[index].left && segementTree[index].right <= right) {
		segementTree[index].lazy_add = (segementTree[index].lazy_add * val) % p;
		segementTree[index].lazy_muti = (segementTree[index].lazy_muti * val) % p;
		segementTree[index].sum = (segementTree[index].sum * val) % p;
		return;
	}
	push_down(index);
	int mid = segementTree[index].left + ((segementTree[index].right - segementTree[index].left) >> 1);
	if(left <= mid) muti(index << 1, left, right, val);
	if(mid < right) muti(index << 1 | 1, left, right, val);
	update(index);
}
void add(int index, int left, int right, int val) {
	if(left <= segementTree[index].left && segementTree[index].right <= right) {
		segementTree[index].lazy_add = (segementTree[index].lazy_add + val) % p;
		segementTree[index].sum = (segementTree[index].sum + segementTree[index].size * val) % p;
		return;
	}
	push_down(index);
	int mid = segementTree[index].left + ((segementTree[index].right - segementTree[index].left) >> 1);
	if(left <= mid) add(index << 1, left, right, val);
	if(mid < right) add(index << 1 | 1, left, right, val);
	update(index);
}
int sum(int index, int left, int right) {
	if(left <= segementTree[index].left && segementTree[index].right <= right) {
		return segementTree[index].sum;
	}
	push_down(index);
	int res = 0;
	int mid = segementTree[index].left + ((segementTree[index].right - segementTree[index].left) >> 1);
	if(left <= mid) res = (res + sum(index << 1, left, right)) % p;
	if(mid < right) res = (res + sum(index << 1 | 1, left, right)) % p;
	return res; 
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m >> p;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	build(1, 1, n);
	while(m--) {
		cin >> op >> x >> y;
		switch(op) {
			case 1: {
				cin >> k;
				muti(1, x, y, k);
				break;
			}
			case 2: {
				cin >> k;
				add(1, x, y, k);
				break;
			}
			case 3: {
				cout << sum(1, x, y) << endl;
				break;
			}
		}
	}
	return 0;
}