Task Fibonacci Machine (fib)

/// https://szkopul.edu.pl/problemset/problem/ii2ZJ7WanCQE4DykUbqLIyVb/site/?key=statement
#include <bits/stdc++.h>
#define vi vector<int>
#define vvi vector<vi>
#define vvvi vector<vvi>

using namespace std;
using int64 = long long;

void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
}

const int mod = 1e9 + 7;

void add_self(int &a, int b) {
  a += b;
  if (a >= mod)
    a -= mod;
}

vvi matrix_mult(const vvi &a, const vvi &b) {
  vvi sol(2, vi(2));
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < 2; ++j)
      for (int k = 0; k < 2; ++k)
        add_self(sol[i][j], (int64)a[i][k] * b[k][j] % mod);
  return sol;
}

vi vector_mult(const vi &a, const vvi &b) {
  vi sol(2);
  for (int i = 0; i < 2; ++i)
    for (int k = 0; k < 2; ++k)
      add_self(sol[i], (int64)a[k] * b[i][k] % mod);
  return sol;
}

vvvi powers;

struct SegTree {
  int Size;
  vvi tree;
  vi lazy;

  SegTree(int N) {
    Size = 1;
    while (Size < N)
      Size <<= 1;
    tree = vvi(Size << 1 | 1, vi(2));
    lazy.resize(Size << 1 | 1);
  }

  void build(int x, int lx, int rx) {
    if (lx == rx) {
      tree[x] = {0, 1};
      return;
    }
    int mid = (lx + rx) >> 1;
    build(x << 1, lx, mid);
    build(x << 1 | 1, mid + 1, rx);
    for (int i = 0; i < 2; ++i)
      tree[x][i] = (tree[x << 1][i] + tree[x << 1 | 1][i]) % mod;
  }

  void propagate(int x, int lx, int rx) {
    if (lx == rx || lazy[x] == 0)
      return;
    for (int i = 0; i < 2; ++i) {
      tree[x << 1 | i] = vector_mult(tree[x << 1 | i], powers[lazy[x]]);
      lazy[x << 1 | i] += lazy[x];
    }
    lazy[x] = 0;
  }

  void update(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr) {
      tree[x] = vector_mult(tree[x], powers[1]);
      ++lazy[x];
      return;
    }
    int mid = (lx + rx) >> 1;
    propagate(x, lx, rx);
    if (st <= mid)
      update(x << 1, lx, mid, st, dr);
    if (mid < dr)
      update(x << 1 | 1, mid + 1, rx, st, dr);
    for (int i = 0; i < 2; ++i)
      tree[x][i] = (tree[x << 1][i] + tree[x << 1 | 1][i]) % mod;
  }

  int query(int x, int lx, int rx, int st, int dr) {
    if (st <= lx && rx <= dr)
      return tree[x][0];
    int mid = (lx + rx) >> 1, ans1 = 0, ans2 = 0;
    propagate(x, lx, rx);
    if (st <= mid)
      ans1 = query(x << 1, lx, mid, st, dr);
    if (mid < dr)
      ans2 = query(x << 1 | 1, mid + 1, rx, st, dr);
    return (ans1 + ans2) % mod;
  }
};

void solve() {
  int N, Q;
  cin >> N >> Q;
  SegTree tree(N);
  tree.build(1, 1, N);
  powers.resize(Q + 1);
  powers[1] = {{0, 1}, {1, 1}};
  for (int i = 2; i <= Q; ++i)
    powers[i] = matrix_mult(powers[i - 1], powers[1]);
  for (int q = 0; q < Q; ++q) {
    char type;
    int l, r;
    cin >> type >> l >> r;
    if (type == 'D')
      tree.update(1, 1, N, l, r);
    else cout << tree.query(1, 1, N, l, r) << '\n';
  }
}

int main() {
  fastIO();
  solve();
  return 0;
}