NOIP前一天想着顺便复习一下矩乘，然后写了个矩阵乘法线段树来做这道题，成功拿下 $2.93s,45.93MB$ 的佳绩（已经进行了一些卡常）。

记录

/*********************************************************************
    程序名:
    版权:
    作者:
    日期: 2024-11-29 10:05
    说明:
*********************************************************************/
#include <bits/stdc++.h>

#define m_p make_pair
#define p_b push_back
#define fst first
#define sec second

#define p_q priority_queue
#define u_map unordered_map

using namespace std;

using ll = long long;
using ull = unsigned long long;
using i128 = __int128;

const int N = 1e5 + 50;

typedef struct {
	ll a[3][3];
	int n, m;
} Matr;

Matr nsm[N << 2], ntg[N << 2], I;
int nl[N << 2], nr[N << 2];
int ar[N];
ll P;

void init() {
	I.n = I.m = 2;
	for (int i = 1; i <= 2; i++) {
		I.a[i][i] = 1;
	}
}

Matr mul(Matr a, Matr b) {
	Matr ans;
	if (b.m == 1) {
		ans.n = 2, ans.m = 1;
		ans.a[1][1] = a.a[1][1] * b.a[1][1] % P + a.a[1][2] * b.a[2][1] % P;
		ans.a[1][1] = ans.a[1][1] > P ? ans.a[1][1] - P : ans.a[1][1];
		ans.a[2][1] = a.a[2][1] * b.a[1][1] % P + a.a[2][2] * b.a[2][1] % P;
		ans.a[2][1] = ans.a[2][1] > P ? ans.a[2][1] - P : ans.a[2][1];
		return ans;
	}
	ans.n = ans.m = 2;
	ans.a[1][1] = a.a[1][1] * b.a[1][1] % P + a.a[1][2] * b.a[2][1] % P;
	ans.a[1][1] = ans.a[1][1] > P ? ans.a[1][1] - P : ans.a[1][1];
	ans.a[1][2] = a.a[1][1] * b.a[1][2] % P + a.a[1][2] * b.a[2][2] % P;
	ans.a[1][2] = ans.a[1][2] > P ? ans.a[1][2] - P : ans.a[1][2];
	ans.a[2][1] = a.a[2][1] * b.a[1][1] % P + a.a[2][2] * b.a[2][1] % P;
	ans.a[2][1] = ans.a[2][1] > P ? ans.a[2][1] - P : ans.a[2][1];
	ans.a[2][2] = a.a[2][1] * b.a[1][2] % P + a.a[2][2] * b.a[2][2] % P;
	ans.a[2][2] = ans.a[2][2] > P ? ans.a[2][2] - P : ans.a[2][2];
	return ans;
}

Matr mad(Matr a, Matr b) {
	Matr ans;
	ans.n = 2, ans.m = 1;
	ans.a[1][1] = a.a[1][1] + b.a[1][1];
	ans.a[1][1] = ans.a[1][1] > P ? ans.a[1][1] - P : ans.a[1][1];
	ans.a[2][1] = a.a[2][1] + b.a[2][1];
	ans.a[2][1] = ans.a[2][1] > P ? ans.a[2][1] - P : ans.a[2][1];
	return ans;
}

bool check(Matr a) {
	if (a.a[1][1] != 1) {
		return false;
	}
	if (a.a[1][2] != 0) {
		return false;
	}
	if (a.a[2][2] != 1) {
		return false;
	}
	if (a.a[2][1] != 0) {
		return false;
	}
	return true;
}

void pushup(int u) {
	nsm[u] = mad(nsm[u << 1], nsm[u << 1 | 1]);
}

void do_mul(int u, Matr k) {
	ntg[u] = mul(k, ntg[u]);
	nsm[u] = mul(k, nsm[u]);
}

void pushdown(int u) {
	if (check(ntg[u])) {
		return;
	}
	do_mul(u << 1, ntg[u]);
	do_mul(u << 1 | 1, ntg[u]);
	ntg[u] = I;
}

void tbuild(int u, int l, int r) {
	nl[u] = l, nr[u] = r, ntg[u] = I;
	if (l == r) {
		nsm[u].n = 2, nsm[u].m = 1;
		nsm[u].a[1][1] = ar[l];
		nsm[u].a[2][1] = 1;
		return;
	}
	int mid = (l + r) >> 1;
	tbuild(u << 1, l, mid);
	tbuild(u << 1 | 1, mid + 1, r);
	pushup(u);
}

Matr tquery(int u, int l, int r) {
	if (l <= nl[u] && nr[u] <= r) {
		return nsm[u];
	}
	pushdown(u);
	if (nr[u << 1] >= l && nl[u << 1 | 1] <= r) {
		return mad(tquery(u << 1, l, r), tquery(u << 1 | 1, l, r));
	}
	if (nr[u << 1] >= l) {
		return tquery(u << 1, l, r);
	}
	return tquery(u << 1 | 1, l, r);
}

void tmul(int u, int l, int r, Matr k) {
	if (l <= nl[u] && nr[u] <= r) {
		do_mul(u, k);
		return;
	}
	pushdown(u);
	if (nr[u << 1] >= l) {
		tmul(u << 1, l, r, k);
	}
	if (nl[u << 1 | 1] <= r) {
		tmul(u << 1 | 1, l, r, k);
	}
	pushup(u);
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n, q;
	cin >> n >> q >> P;
	for (int i = 1; i <= n; i++) {
		cin >> ar[i];
	}
	init();
	tbuild(1, 1, n);
	while (q--) {
		int opt, l, r;
		ll k;
		cin >> opt >> l >> r;
		if (opt == 1) {
			cin >> k;
			Matr qwq;
			qwq.n = qwq.m = 2;
			qwq.a[1][1] = k % P;
			qwq.a[2][1] = qwq.a[1][2] = 0;
			qwq.a[2][2] = 1;
			tmul(1, l, r, qwq);
		} else if (opt == 2) {
			cin >> k;
			Matr qwq;
			qwq.n = qwq.m = 2;
			qwq.a[1][1] = qwq.a[2][2] = 1;
			qwq.a[2][1] = 0;
			qwq.a[1][2] = k % P;
			tmul(1, l, r, qwq);
		} else {
			cout << tquery(1, l, r).a[1][1] << endl;
		}
	}

	return 0;
}