线段树2分块做法被卡常了求条

#include<bits/stdc++.h>
using namespace std;
int n , q , mod , mk[100005];
int a[100005];
struct node{
	int l , r;
	int sum;
	int add , mul;
} p[100005];
inline void pushdown(int id){
	if(p[id].mul != 1 || p[id].add != 0){
		p[id].sum = 0;
		for(int i = p[id].l ; i <= p[id].r ; i++){
			a[i] = ((long long)a[i] * p[id].mul % mod + p[id].add) % mod;
			p[id].sum = (p[id].sum + a[i]) % mod;
		}
		p[id].mul = 1;
		p[id].add = 0;
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> q >> mod;
	for(int i = 1 ; i <= n ; i++) cin >> a[i];
	int len = sqrt(n);  int len2 = n / len;
	for(int i = 1 ; i < len ; i++){
		p[i].l = p[i - 1].r + 1;
		p[i].r = i * len2;
	}
	p[len].l = p[len - 1].r + 1;
	p[len].r = n;
	for(int i = 1 ; i <= len ; i++){
		p[i].sum = 0;
		for(int j = p[i].l ; j <= p[i].r ; j++){
			p[i].sum = (p[i].sum + a[j]) % mod;
			mk[j] = i;
		}
		p[i].mul = 1; 
		p[i].add = 0;
	}
	while(q--){
		int op , x , y , k;
		cin >> op >> x >> y;
		if(op <= 2){
			cin >> k;
			if(op == 2){
				int L = mk[x] , R = mk[y];
				if(L == R){
					pushdown(L);
					for(int i = x ; i <= y ; i++){
						p[L].sum = (p[L].sum + k) % mod;
						a[i] = (a[i] + k) % mod;
					}
				}
				else{
					for(int i = L + 1 ; i <= R - 1 ; i++){
						p[i].add = (p[i].add + k) % mod;
						p[i].sum = (p[i].sum + (long long)k * (p[i].r - p[i].l + 1)) % mod;
					}
					pushdown(L);
					for(int i = x ; i <= p[L].r ; i++){
						p[L].sum = (p[L].sum + k) % mod;
						a[i] = (a[i] + k) % mod;
					}
					pushdown(R);
					for(int i = p[R].l ; i <= y ; i++){
						p[R].sum = (p[R].sum + k) % mod;
						a[i] = (a[i] + k) % mod;
					}
				}
			}
			else{
				int L = mk[x] , R = mk[y];
				if(L == R){
					pushdown(L);
					for(int i = x ; i <= y ; i++){
						p[L].sum = (p[L].sum + (long long)a[i] * (k - 1 + mod)) % mod;
						a[i] = (long long)a[i] * k % mod;
					}
				}
				else{
					for(int i = L + 1 ; i <= R - 1 ; i++){
						p[i].mul = (long long)p[i].mul * k % mod;
						p[i].add = (long long)p[i].add * k % mod;
						p[i].sum = (long long)p[i].sum * k % mod;
					}
					pushdown(L);
					for(int i = x ; i <= p[L].r ; i++){
						p[L].sum = (p[L].sum + (long long)a[i] * (k - 1 + mod)) % mod;
						a[i] = (long long)a[i] * k % mod;
					}
					pushdown(R);
					for(int i = p[R].l ; i <= y ; i++){
						p[R].sum = (p[R].sum + (long long)a[i] * (k - 1 + mod)) % mod;
						a[i] = (long long)a[i] * k % mod;
					}
				}
			}
		}
		else{
			int L = mk[x] , R = mk[y];
			int res = 0;
			if(L == R){
				for(int i = x ; i <= y ; i++) 
					res = (res + ((long long)a[i] * p[L].mul + p[L].add)) % mod;
			}
			else{
				for(int i = L + 1 ; i <= R - 1 ; i++) 
					res = (res + p[i].sum) % mod;
				for(int i = x ; i <= p[L].r ; i++) 
					res = (res + ((long long)a[i] * p[L].mul + p[L].add)) % mod;
				for(int i = p[R].l ; i <= y ; i++) 
					res = (res + ((long long)a[i] * p[R].mul + p[R].add)) % mod;
			}
			cout << res << "\n";
		}
	}
	return 0;
}