#853. 线性函数

线性函数

题目描述

众所周知,一次函数可以表示为如下形式:f(x)=kx+bf(x) = kx + b

现有 nn 个一次函数 fi(x)=kix+bif_i(x)=k_ix+b_i,需要对这 nn 个一次函数执行 mm 次操作,每次操作为下列格式之一:

  1. M i K B:代表把第 ii 个线性函数改为:fi(x)=Kx+Bf_i(x)=Kx+B
  2. Q l r x:求 fr(fr1(...fl(x)))f_r(f_{r-1}(...f_l(x))) 的值,并对 109+710^9+7 取模。

输入格式

第一行两个整数 n,mn, m

接下来 nn 行,每行两个整数 ki,bik_i, b_i

接着是 mm 行询问或修改,每行的格式为 M i K B 或者 Q l r x

输出格式

对于每个 Q 操作,输出一行答案(对 109+710^9+7 取模)。

5 5
4 2
3 6
5 7
2 6
7 5
Q 1 5 1
Q 3 3 2
M 3 10 6
Q 1 4 3
Q 3 4 4
1825
17
978
98

数据范围

1n,m2×1051 \le n, m \le 2 \times 10^5

1lrn1 \le l \le r \le n

0ki,bi,x<109+70 \le k_i, b_i, x < 10^9+7

题目来源:BZOJ4499.