求条悬关

#include<bits/stdc++.h>
using namespace std;
int n , q ;
long long m;
long long a[100005];
struct node{
	int left , right;
	long long value = 0 , multi = 1 , add = 0;
}tree[400005];
void build(int root , int l , int r ) {
	tree[root].left = l , tree[root].right = r;
	if(tree[root].left == tree[root].right) {
		tree[root].value = a[l] % m;
		return;
	}
	int mid = (l + r) / 2 ; 
	build(2 * root , l , mid);
	build(2 * root + 1 , mid + 1 , r);
	tree[root].value =(tree[2 * root].value + tree[2 * root + 1].value) % m;
}
void spread(int root) {
	long long lazyadd = tree[root].add , lazymulti = tree[root].multi;
	tree[root].add = 0 , tree[root].multi = 1;
	if(lazyadd != 0 || lazymulti != 1) {
		tree[2 * root].multi = (tree[2 * root].multi * lazymulti) % m;
		tree[2 * root + 1].multi = (tree[2 * root + 1].multi * lazymulti) % m;
		tree[2 * root].add = (tree[2 * root].add * lazymulti + lazyadd) % m;
		tree[2 * root + 1].add = (tree[2 * root + 1].add * lazymulti + lazyadd) % m;
		tree[2 * root].value = (tree[2 * root].value * lazymulti) % m;
		tree[2 * root + 1].value = (tree[2 * root].value * lazymulti) % m;
		tree[2 * root].value = (tree[2 * root].value + lazyadd * (tree[2 * root].right - tree[2 * root].left + 1)) % m;
		tree[2 * root + 1].value = (tree[2 * root + 1].value + lazyadd * (tree[2 * root + 1].right - tree[2 * root + 1].left + 1)) % m;
	}
}
void update_ride(int root , int l , int r , long long x) {
	if(tree[root].left >= l && tree[root].right <= r) {
		tree[root].multi = (tree[root].multi * x) % m;
		tree[root].value = (tree[root].value * x) % m;
		tree[root].add = (tree[root].add * x) % m; 
		return;
	}
	spread(root);
	int mid = (tree[root].left + tree[root].right) / 2;
	if(l <= mid) update_ride(2 * root , l , r , x); 
	if(r > mid) update_ride(2 * root + 1 , l , r , x);
	tree[root].value = (tree[2 * root].value + tree[2 * root + 1].value) % m;
}
void update_add(int root , int l , int r , long long x) {
	if(tree[root].left >= l && tree[root].right <= r) {
		tree[root].add = (tree[root].add + x) % m;
		tree[root].value = (tree[root].value + x * (tree[root].right - tree[root].left + 1) % m) % m;
		return;
	}
	spread(root);
	int mid = (tree[root].left + tree[root].right) / 2;
	if(l <= mid) update_add(2 * root , l , r , x);
	if(r > mid) update_add(2 * root + 1 , l , r , x);
	tree[root].value = (tree[2 * root].value + tree[2 * root + 1].value) % m;
}
long long query(int root , int l , int r) {
	if(tree[root].left >= l && tree[root].right <= r) {
		return tree[root].value;
	}
	spread(root);
	int mid = (tree[root].left + tree[root].right) / 2 ;
	long long ans = 0;
	if(l <= mid) ans = (ans + query(2 * root , l , r)) % m;
	if(r > mid) ans = (ans + query(2 * root + 1 , l , r)) % m;
	return ans;
}
int main() {
	cin >> n >> q >> m;
	for(int i = 1 ; i <= n ; i++) {
		cin >> a[i];
	}
	build(1 , 1 , n);
	while(q--) {
		int op , l , r ;
		long long x;
		cin >> op;
		if(op == 1){
			cin >> l >> r >> x;
			update_ride(1 , l , r , x);
		}if(op == 2) {
			cin >> l >> r >> x;
			update_add(1 , l , r , x);
		}if(op == 3) {
			cin >> l >> r;
			cout << query(1 , l , r) << "\n"; 
		}
/*
		for(int i = 1 ; i <= n; i ++) {
			cout << query(1 , i , i) << " ";
		}
		cout << "\n";
*/
	}
	return 0;
}