这个小丑看了好久题目才发现保证 \(t\) 不降。
好像与其他题解做法稍有不同。
思路
其他题解的标记做法非常复杂，怎么办。
我们可以使用适用性可加强大的矩阵乘法。
我们考虑维护：
\[\begin{bmatrix}
\sum v&\sum a\times b&\sum a&\sum b&len\\
\end{bmatrix}
\]
分别表示 \(v\) 的和， \(a\times b\) 的和， \(a\) 的和， \(b\) 的和，与区间长度。
分操作考虑。
时间往后移
也就是所有的 \(v\) 需要加上若干倍的 \(a\times b\)。
那么在矩阵上也就是乘上：
\[\begin{bmatrix}
1&0&0&0&0\\
t-last&1&0&0&0\\
0&0&1&0&0\\
0&0&0&1&0\\
0&0&0&0&1\\
\end{bmatrix}
\]
其中 \(t\) 表示此时的时间，\(last\) 表示上一个时间。
区间加 \(v\)
在矩阵上为：
\[\begin{bmatrix}
1&0&0&0&0\\
0&1&0&0&0\\
0&0&1&0&0\\
0&0&0&1&0\\
z&0&0&0&1\\
\end{bmatrix}
\]
区间加 \(a\)
在矩阵上为：
\[\begin{bmatrix}
1&0&0&0&0\\
0&1&0&0&0\\
0&0&1&0&0\\
0&z&0&1&0\\
0&0&z&0&1\\
\end{bmatrix}
\]
区间加 \(b\)
在矩阵上为：
\[\begin{bmatrix}
1&0&0&0&0\\
0&1&0&0&0\\
0&z&1&0&0\\
0&0&0&1&0\\
0&0&0&z&1\\
\end{bmatrix}
\]
应当都是比较容易理解的。
从这里就可以看出矩阵乘法的好处了，更加容易思考与实现。
然后直接使用线段树维护即可。
时间复杂度：\(O(5^3n\log n)\)
Code
有一些细节。
如果直接这么写的话会只有 \(\text{60pts}\)。
会有一些点 \(\text{TLE}\)。
合理减少取模后。
可以得到 \(\text{90pts}\)。
将矩阵循环展开，减少一直为 \(0\) 的位置。
就可以过了。
当然，如果你经常写数据结构维护矩阵，这些都是基本的（都是因为一般朴素的会被卡。
代码比较冗长，但很好写（最长的是复制粘贴的循环展开）。
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(x, y) make_pair(x, y)
#define fro(i, x, y) for(int i = (x);i <= (y);i++)
#define pre(i, x, y) for(int i = (x);i >= (y);i--)
#define dbg cerr << "Line " << __LINE__ << ": "
#define EVAL(x) #x " = " << (x)
typedef int64_t i64;
typedef uint32_t u32;
typedef uint64_t u64;
typedef __int128_t i128;
typedef __uint128_t u128;
typedef pair<int, int> PII;
bool ed;
const int N = 200010;
const int mod = 1e8 + 7;
int n, m, vis[N<<1];
inline void add(i64 &x, int y)
{ x = (x + y) + (x + y >= mod ? -mod : 0); }
struct Mat
{
i64 a[5][5]{};
inline void init() { a[0][0] = a[1][1] = a[2][2] = a[3][3] = a[4][4] = 1; }
inline void init(i64 v_, i64 ab_, i64 a_, i64 b_)
{ a[0][0] = v_, a[0][1] = ab_, a[0][2] = a_, a[0][3] = b_, a[0][4] = 1; }
inline void clear() { memset(a, 0, sizeof a); }
inline Mat operator*(const Mat &tmp) const
{
Mat c;
c.a[0][0] = (a[0][0] * tmp.a[0][0] + a[0][1] * tmp.a[1][0] + a[0][2] * tmp.a[2][0] + a[0][3] * tmp.a[3][0] + a[0][4] * tmp.a[4][0]) % mod;
c.a[0][1] = (a[0][0] * tmp.a[0][1] + a[0][1] * tmp.a[1][1] + a[0][2] * tmp.a[2][1] + a[0][3] * tmp.a[3][1] + a[0][4] * tmp.a[4][1]) % mod;
c.a[0][2] = (a[0][0] * tmp.a[0][2] + a[0][1] * tmp.a[1][2] + a[0][2] * tmp.a[2][2] + a[0][3] * tmp.a[3][2] + a[0][4] * tmp.a[4][2]) % mod;
c.a[0][3] = (a[0][0] * tmp.a[0][3] + a[0][1] * tmp.a[1][3] + a[0][2] * tmp.a[2][3] + a[0][3] * tmp.a[3][3] + a[0][4] * tmp.a[4][3]) % mod;
c.a[0][4] = (a[0][0] * tmp.a[0][4] + a[0][1] * tmp.a[1][4] + a[0][2] * tmp.a[2][4] + a[0][3] * tmp.a[3][4] + a[0][4] * tmp.a[4][4]) % mod;
c.a[1][0] = (a[1][0] * tmp.a[0][0] + a[1][1] * tmp.a[1][0] + a[1][2] * tmp.a[2][0] + a[1][3] * tmp.a[3][0] + a[1][4] * tmp.a[4][0]) % mod;
c.a[1][1] = (a[1][0] * tmp.a[0][1] + a[1][1] * tmp.a[1][1] + a[1][2] * tmp.a[2][1] + a[1][3] * tmp.a[3][1] + a[1][4] * tmp.a[4][1]) % mod;
c.a[2][0] = (a[2][0] * tmp.a[0][0] + a[2][1] * tmp.a[1][0] + a[2][2] * tmp.a[2][0] + a[2][3] * tmp.a[3][0] + a[2][4] * tmp.a[4][0]) % mod;
c.a[2][1] = (a[2][0] * tmp.a[0][1] + a[2][1] * tmp.a[1][1] + a[2][2] * tmp.a[2][1] + a[2][3] * tmp.a[3][1] + a[2][4] * tmp.a[4][1]) % mod;
c.a[2][2] = (a[2][0] * tmp.a[0][2] + a[2][1] * tmp.a[1][2] + a[2][2] * tmp.a[2][2] + a[2][3] * tmp.a[3][2] + a[2][4] * tmp.a[4][2]) % mod;
c.a[3][0] = (a[3][0] * tmp.a[0][0] + a[3][1] * tmp.a[1][0] + a[3][2] * tmp.a[2][0] + a[3][3] * tmp.a[3][0] + a[3][4] * tmp.a[4][0]) % mod;
c.a[3][1] = (a[3][0] * tmp.a[0][1] + a[3][1] * tmp.a[1][1] + a[3][2] * tmp.a[2][1] + a[3][3] * tmp.a[3][1] + a[3][4] * tmp.a[4][1]) % mod;
c.a[3][3] = (a[3][0] * tmp.a[0][3] + a[3][1] * tmp.a[1][3] + a[3][2] * tmp.a[2][3] + a[3][3] * tmp.a[3][3] + a[3][4] * tmp.a[4][3]) % mod;
c.a[4][0] = (a[4][0] * tmp.a[0][0] + a[4][1] * tmp.a[1][0] + a[4][2] * tmp.a[2][0] + a[4][3] * tmp.a[3][0] + a[4][4] * tmp.a[4][0]) % mod;
c.a[4][1] = (a[4][0] * tmp.a[0][1] + a[4][1] * tmp.a[1][1] + a[4][2] * tmp.a[2][1] + a[4][3] * tmp.a[3][1] + a[4][4] * tmp.a[4][1]) % mod;
c.a[4][2] = (a[4][0] * tmp.a[0][2] + a[4][1] * tmp.a[1][2] + a[4][2] * tmp.a[2][2] + a[4][3] * tmp.a[3][2] + a[4][4] * tmp.a[4][2]) % mod;
c.a[4][3] = (a[4][0] * tmp.a[0][3] + a[4][1] * tmp.a[1][3] + a[4][2] * tmp.a[2][3] + a[4][3] * tmp.a[3][3] + a[4][4] * tmp.a[4][3]) % mod;
c.a[4][4] = (a[4][0] * tmp.a[0][4] + a[4][1] * tmp.a[1][4] + a[4][2] * tmp.a[2][4] + a[4][3] * tmp.a[3][4] + a[4][4] * tmp.a[4][4]) % mod;
return c;
}
inline Mat operator+(const Mat &tmp) const
{ Mat c; fro(i, 0, 4) c.a[0][i] = (a[0][i] + tmp.a[0][i]) - (a[0][i] + tmp.a[0][i] >= mod ? mod : 0); return c; }
} t[N<<1], tg[N<<1], mat[5];
#define ls (mid<<1)
#define rs (mid<<1|1)
inline void mo(i64 &x)
{ x = (x % mod + mod) % mod; }
inline void mat1(int t) { mat[1].a[1][0] = t; }
inline void mat2(int t) { mat[2].a[3][1] = mat[2].a[4][2] = t; }
inline void mat3(int t) { mat[3].a[2][1] = mat[3].a[4][3] = t; }
inline void mat4(int t) { mat[4].a[4][0] = t; }
inline void push(int p, const Mat &k)
{ t[p] = t[p] * k, tg[p] = tg[p] * k, vis[p] = 1; }
inline void pdo(int p, int mid)
{
if(vis[p])
{
push(ls, tg[p]), push(rs, tg[p]);
tg[p].clear(), tg[p].init(), vis[p] = 0;
}
}
inline void update(int p, int l, int r, int L, int R, int op)
{
if(L <= l && r <= R) return push(p, mat[op]);
int mid = (l + r) >> 1; pdo(p, mid);
if(mid >= L) update(ls, l, mid, L, R, op);
if(mid < R) update(rs, mid + 1, r, L, R, op);
t[p] = t[ls] + t[rs];
}
inline int ask(int p, int l, int r, int L, int R)
{
if(L <= l && r <= R) return t[p].a[0][0];
int mid = (l + r) >> 1; pdo(p, mid); i64 sum{};
if(mid >= L) add(sum, ask(ls, l, mid, L, R));
if(mid < R) add(sum, ask(rs, mid + 1, r, L, R));
return sum;
}
inline void build(int p, int l, int r)
{
tg[p].init();
if(l == r)
{
i64 v, a, b;
cin >> v >> a >> b;
mo(v), mo(a), mo(b);
t[p].init(v, a * b % mod, a, b);
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
t[p] = t[ls] + t[rs];
}
inline void solve()
{
cin >> n >> m;
build(1, 1, n); i64 last = 0;
mat[1].init(), mat[2].init();
mat[3].init(), mat[4].init();
fro(i, 1, m)
{
i64 op, t_, x, y, z;
cin >> op >> t_ >> x >> y;
if(t_ != last) mat1(t_ - last), push(1, mat[1]), last = t_;
if(op != 1) cin >> z, mo(z);
if(op == 1) cout << ask(1, 1, n, x, y) << "\n";
if(op == 2) mat2(z), update(1, 1, n, x, y, 2);
if(op == 3) mat3(z), update(1, 1, n, x, y, 3);
if(op == 4) mat4(z), update(1, 1, n, x, y, 4);
}
}
bool st;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
double Mib = fabs((&ed-&st)/1048576.), Lim = 500;
cerr << " Memory: " << Mib << "\n", assert(Mib<=Lim);
solve();
return 0;
}