Gọi ~F_{x, y}~ là một dãy dài vô hạn sao cho:

• ~F_{x, y, 0} = x~
• ~F_{x, y, 1} = y~
• ~F_{x, y, i} = 2 * F_{x, y, i - 2} + F_{x, y, i - 1}~

Với ~F_{x, y, i}~ là phần tử thứ ~i~ của dãy ~F_{x, y}~

Theo đề bài: ~f = F_{0, 1}~

Nhận xét: ~F_{x, y, i} = F_{1, 0, i} * x + F_{0, 1, i} * y~

Xét truy vấn ~1~ ~l~ ~r~ ~k~: với mỗi ~i~ thuộc đoạn ~[l, r]~ gán ~a_i = F_{f_{k - 1}, f_k, i} = F_{1, 0, i} * f_{k - 1} + F_{0, 1, i} * f_k~ (*)

Ở đây các dãy ~F_{0, 1}~ và ~F_{1, 0}~ là cố định và chỉ cần dùng đến ~n~ phần tử đầu tiên của dãy, các giá trị ~f_k, f_{k - 1}~ cũng có thể tính được trong ~O(log(n))~ hoặc ~O(1)~.

Dựa vào phương trình (*) và các tính chất vừa nêu, có thể dùng segment tree với lazy propagation để thực hiện các truy vấn.

Để tính được ~f_k~ và ~f_{k - 1}~ dùng phương pháp nhân ma trận ~O(log(n))~ hoặc ứng dụng pisano period ~O(1)~, cụ thể đối với bài này ta có ~f_i = f_{(i \mod 360)}~

Code mẫu

#include <bits/stdc++.h>

#define fi first
#define se second
#define For(i, a, b) for (int i=a;i<=b;++i)
#define Ford(i, a, b) for(int i=a;i>=b;--i)

using namespace std;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef array<int, 3> arr;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef array<array<ll, 2>, 2> matrix;

const int N = 2 * 1e5 + 5;
const ll mod = 1058375681;

ll a[N], b[N];
ll sum[4 * N], sa[4 * N], sb[4 * N];
ii laz[4 * N];

void build(int k, int l, int r) {
    if (l == r) {
        sa[k] = a[l];
        sb[k] = b[l];
        return;
    }
    int m = (l + r) / 2;
    build(k * 2, l, m); build(k * 2 + 1, m + 1, r);
    sa[k] = (sa[k * 2] + sa[k * 2 + 1]) % mod;
    sb[k] = (sb[k * 2] + sb[k * 2 + 1]) % mod;
}

void add(int k, ll x, ll y) {
    sum[k] = (sa[k] * x % mod + sb[k] * y) % mod;
    laz[k] = {x, y};
}

void down(int k) {
    if (!laz[k].fi && !laz[k].se) return;
    add(k * 2, laz[k].fi, laz[k].se);
    add(k * 2 + 1, laz[k].fi, laz[k].se);
    laz[k] = {0, 0};
}

void upd(int k, int l, int r, int i, int j, ll x, ll y) {
    if (r < i || l > j) return;
    if (l >= i && r <= j) {
        add(k, x, y);
        return;
    }
    down(k);
    int m = (l + r) / 2;
    upd(k * 2, l, m, i, j, x, y);
    upd(k * 2 + 1, m + 1, r, i, j, x, y);
    sum[k] = (sum[k * 2] + sum[k * 2 + 1]) % mod;
}

ll get(int k, int l, int r, int i, int j) {
    if (r < i || l > j) return 0;
    if (l >= i && r <= j) return sum[k];
    down(k);
    int m = (l + r) / 2;
    return (get(k * 2, l, m, i, j) + get(k * 2 + 1, m + 1, r, i, j)) % mod;
}


void solve()
{
    int n, q; cin >> n >> q;

    int m = 200000;
    a[0] = 1;
    For(i, 2, m) a[i] = (a[i - 1] + 2 * a[i - 2]) % mod;
    b[1] = 1;
    For(i, 2, m) b[i] = (b[i - 1] + 2 * b[i - 2]) % mod;

    build(1, 1, n);

    while (q--) {
        int t, l, r; ll k;
        cin >> t >> l >> r;
        if (t == 1) {
            cin >> k;
            upd(1, 1, n, l, r, b[(k - 1) % 360], b[k % 360]);
        }
        else {
            cout << get(1, 1, n, l, r) << "\n";
        }
    }
}

int main()
{
    // freopen("input.txt","r",stdin);
//  freopen(".out","w",stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);

    solve();

    return 0;
}