萌新求助线段树

#include <iostream>
#include <cstdio>
typedef long long ll;
const int MAXN = 1e5+10;
struct Tree{
	int l, r;
	ll val, sign1, sign2;
}t[MAXN*4];

int n, m;
ll s[MAXN], p;

#define ls (k*2)
#define rs (k*2+1)
void build(int k, int l, int r){
	t[k].l = l, t[k].r = r;
	t[k].sign1 = 1;
	if(l==r){
		t[k].val = s[l]%p;
		return;
	}
	int mid = (l+r)>>1;
	build(ls, l, mid);
	build(rs, mid+1, r);
	t[k].val = (t[ls].val+t[rs].val)%p;
}
void spread(int k){
	if(t[k].sign1!=1){
		t[ls].val = t[ls].val*t[k].sign1%p;
		t[rs].val = t[rs].val*t[k].sign1%p;
		t[ls].sign1 = t[ls].sign1*t[k].sign1%p;
		t[rs].sign1 = t[rs].sign1*t[k].sign1%p;
		t[k].sign1 = 1;
	}
	if(t[k].sign2){
		t[ls].val = (t[ls].val+t[k].sign2*(t[ls].r-t[ls].l+1))%p;
		t[rs].val = (t[rs].val+t[k].sign2*(t[rs].r-t[rs].l+1))%p;
		t[ls].sign2 = (t[ls].sign2+t[k].sign2)%p;
		t[rs].sign2 = (t[rs].sign2+t[k].sign2)%p;
		t[k].sign2 = 0;
	}
}
void modify1(int k, int l, int r, ll val){
	if(l<=t[k].l && t[k].r<=r){
		t[k].val = t[k].val*val%p;
		t[k].sign1 = t[k].sign1*val%p;
		return;
	}
	spread(k);
	int mid = (t[k].l+t[k].r)>>1;
	if(l<=mid)
		modify1(ls, l, r, val);
	if(r>mid)
		modify1(rs, l, r, val);
	t[k].val = (t[ls].val+t[rs].val)%p;
}
void modify2(int k, int l, int r, ll val){
	if(l<=t[k].l && t[k].r<=r){
		t[k].val = (t[k].val+val*(t[k].r-t[k].l+1))%p;
		t[k].sign2 = (t[k].sign2+val)%p;
		return;
	}
	spread(k);
	int mid = (t[k].l+t[k].r)>>1;
	if(l<=mid)
		modify2(ls, l, r, val);
	if(r>mid)
		modify2(rs, l, r, val);
	t[k].val = (t[ls].val+t[rs].val)%p;
}
ll ask(int k, int l, int r){
	if(l<=t[k].l && t[k].r<=r)
		return t[k].val;
	spread(k);
	int mid = (t[k].l+t[k].r)>>1;
	ll res = 0;
	if(l<=mid)
		res = (res+ask(ls, l, r))%p;
	if(r>mid)
		res = (res+ask(rs, l, r))%p;
	return res;
}
int main(){
	freopen("input.txt", "r", stdin);
	scanf("%d%d%lld", &n, &m, &p);
	for(int i=1; i<=n; ++i)
		scanf("%lld", s+i);
	build(1, 1, n);
	int a, x, y;
	ll k;
	for(int i=1; i<=m; ++i){
		scanf("%d", &a);
		if(a==1){
			scanf("%d%d%lld", &x, &y, &k);
			modify1(1, x, y, k);
		}
		if(a==2){
			scanf("%d%d%lld", &x, &y, &k);
			modify2(1, x, y, k);
		}
		if(a==3){
			scanf("%d%d", &x, &y);
			printf("%lld\n", ask(1, x, y));
		}
	}
	return 0;
}