#include <bits/stdc++.h>
using namespace std;
int n,m;
long long mod ;
struct Mat{
    long long a11 = 1, a12 = 0, a21 = 0, a22 = 1;
    Mat operator*(const Mat &b) const{
        Mat res;
        res.a11 = (a11 * b.a11 + a12 * b.a21)%mod;
        res.a12 = (a11 * b.a12 + a12 * b.a22)%mod;
        res.a21 = (a21 * b.a11 + a22 * b.a21)%mod;
        res.a22 = (a21 * b.a12 + a22 * b.a22)%mod;
        return res;
    }
    bool isi(){
        return a11 == 1 && a12 == 0 && a22 == 1 && a21 == 0;
    }
};
long long a[100010];
struct Segtree{
    long long tree[400040];
    Mat lazy[400040];
    void init(int size){


        build(1,1,size);
    }
    void build(int p,int l ,int r){
        if(l == r){
            tree[p] = a[l];
            lazy[p] = Mat();
            return;
        }
        int mid = (l + r) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
        tree[p] = (tree[p * 2] + tree[p * 2 + 1])%mod;
    }
    void pushdown(int p,int l,int r){
        if(!lazy[p].isi()){
            int mid = (l + r) / 2;
            tree[p*2] = (lazy[p].a11 * tree[p*2] + lazy[p].a12 * (mid - l + 1))%mod;
            tree[p*2+1] = (lazy[p].a11 * tree[p*2+1] + lazy[p].a12 * (r - mid))%mod;
            lazy[p*2] = lazy[p] * lazy[p*2];
            lazy[p*2+1] = lazy[p] * lazy[p*2+1];
            lazy[p] = Mat();
        }
    }
    void add(int p,int l,int r,int ql,int qr,int val){
        if(ql <= l && r <= qr){
            tree[p] = (tree[p] + val * (r-l+1)) % mod;
            Mat tmp;
            tmp.a11 = 1;
            tmp.a22 = 1;
            tmp.a12 = val;
            lazy[p] = tmp * lazy[p];
            return ;
        }
        pushdown(p,l,r);
        int mid = (l + r) / 2;
        if(ql <= mid){
            add(p * 2, l, mid, ql, qr, val);
        }
        if(mid < qr){
            add(p * 2 + 1, mid + 1, r, ql, qr, val);
        }
        tree[p] = (tree[p * 2] + tree[p * 2 + 1])%mod;
    }
    void mul(int p,int l,int r,int ql,int qr,int val){
        if(ql <= l && r <= qr){
            tree[p] = (tree[p] * val) % mod;
            Mat tmp;
            tmp.a11 = val;
            tmp.a22 = 1;
            lazy[p] = tmp * lazy[p];
            return ;
        }
        pushdown(p,l,r);
        int mid = (l + r) / 2;
        if(ql <= mid){
            mul(p * 2, l, mid, ql, qr, val);
        }
        if(mid < qr){
            mul(p * 2 + 1, mid + 1, r, ql, qr, val);
        }
        tree[p] = (tree[p * 2] + tree[p * 2 + 1])%mod;
    }
    long long query(int p,int l,int r,int ql,int qr){
        if(ql <= l && r <= qr){
            return tree[p];
        }
        pushdown(p,l,r);
        int mid = (l + r) / 2;
        long long res = 0;
        if(ql <= mid){
            res += query(p * 2, l, mid, ql, qr);
        }
        if(mid < qr){
            res += query(p * 2 + 1, mid + 1, r, ql, qr);
        }
        return res%mod;
    }
};
Segtree st;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

//    freopen("test1.in","r",stdin);
//    freopen("test1.out","w",stdout);
    // 6 4 10000000 1 2 3 4 5 6 2 2 6 4 3 1 4 2 1 5 2 3 2 5
    cin >> n >> m >> mod;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    st.init( n);
    while(m--){
        int op;
        cin >> op;
        if(op == 1){
            int l,r,val;
            cin >> l >> r >> val;
            st.mul(1,1,n,l,r,val);
        }else if(op == 2){
            int l,r,val;
            cin >> l >> r >> val;
            st.add(1,1,n,l,r,val);
        }else if(op == 3){
            int l,r;
            cin >> l >> r;
            cout << st.query(1,1,n,l,r) << '\n';
        }

//        for(int i = 1; i<= n; i++){
//            cout << st.query(1,1,n,i,i) << ' ';
//        }
//        cout << endl;
    }
    return 0;
}

各位帅哥，帮我看看，为啥TLE60！！！

#include <bits/stdc++.h>
using namespace std;
int n, m, mod;
struct Matrix {
	long long a[3][3];
	Matrix() {
		a[1][1] = a[2][2] = 1;
		a[1][2] = a[2][1] = 0;
	}
	Matrix operator*(const Matrix& b) {
		Matrix res;
		for (int i = 1; i <= 2; i++) {
			for (int j = 1; j <= 2; j++) {
				res.a[i][j] = 0;
				for (int k = 1; k <= 2; k++) {
					res.a[i][j] += a[i][k] * b.a[k][j] % mod;
				}
				res.a[i][j] %= mod;
			}
		}
		return res;
	}
	bool flag() {
		if (a[1][1] == 1 && a[1][2] == 0 && a[2][1] == 0 && a[2][2] == 1) {
			return false;
		}
		return true;
	}
};
struct Segtree {
	std::vector<long long> tree;
	std::vector<Matrix> lazy;
	void init(std::vector<long long> &a) {
		tree.resize(4 * n + 1);
		lazy.resize(4 * n + 1);
		build(1, 1, n, a);
	}
	void build(int p, int l, int r, std::vector<long long> &a) {
		if (l == r) {
			tree[p] = a[l];
			return;
		}
		int mid = (l + r) / 2;
		build(p * 2, l, mid, a);
		build(p * 2 + 1, mid + 1, r, a);
		tree[p] = (tree[p * 2] + tree[p * 2 + 1]) % mod;
	}
	void pushdown(int p, int l, int r) {
		if (lazy[p].flag()) {
			int mid = (l + r) / 2;
			tree[p * 2] = (tree[p * 2] * lazy[p].a[1][1] +  lazy[p].a[1][2] * (mid - l + 1)) % mod;
			tree[p * 2 + 1] = (tree[p * 2 + 1] * lazy[p].a[1][1] +  lazy[p].a[1][2] * (r - mid)) % mod;
			lazy[p * 2] = lazy[p] * lazy[p * 2] ;
			lazy[p * 2 + 1] = lazy[p] * lazy[p * 2 + 1] ;
			lazy[p] = Matrix();
		}
	}
	void update(int p, int l, int r, int ql, int qr, Matrix val) {
		if (l > qr || r < ql) {
			return;
		}
		if (l >= ql && r <= qr) {
			tree[p] = (tree[p] * val.a[1][1] + val.a[1][2] * (r - l + 1)) % mod;
			lazy[p] = val * lazy[p];
			return;
		}
		pushdown(p, l, r);
		int mid = (l + r) / 2;
		update(p * 2, l, mid, ql, qr, val);
		update(p * 2 + 1, mid + 1, r, ql, qr, val);
		tree[p] = (tree[p * 2] + tree[p * 2 + 1]) % mod;
	}
	long long query(int p, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) {
			return 0;
		}
		if (l >= ql && r <= qr) {
			return tree[p];
		}
		pushdown(p, l, r);
		int mid = (l + r) / 2;
		return (query(p * 2, l, mid, ql, qr) + query(p * 2 + 1, mid + 1, r, ql, qr)) % mod;
	}
} tree;
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n >> m >> mod;
	std::vector<long long> a(n + 1);
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}
	tree.init(a);
	Matrix val;
	for (int i = 1; i <= m; i++) {
		long long op, l, r, k;
		std::cin >> op >> l >> r;
		if (op == 1) {
			std::cin >> k;
			val.a[1][1] = k;
			val.a[1][2] = 0;
			tree.update(1, 1, n, l, r, val);
		} else if (op == 2) {
			std::cin >> k;
			val.a[1][1] = 1;
			val.a[1][2] = k;
			tree.update(1, 1, n, l, r, val);
		} else {
			std::cout << tree.query(1, 1, n, l, r) << '\n';
		}
	}
	return 0;
}