Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom1年前

09/11
12:51
线段树

[bzoj 4499] 线性函数

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

小C最近在学习线性函数,线性函数可以表示为:f(x) = kx + b。现在小C面前有n个线性函数fi(x)=kix+bi ,他对这n个线性函数执行m次操作,每次可以:
1.M i K B 代表把第i个线性函数改为:fi(x)=kx+b 。
2.Q l r x 返回fr(fr-1(...fl(x)))  mod  10^9+7 。

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

第一行两个整数n, m (1 <= n, m <= 200,000)。
接下来n行,每行两个整数ki, bi。
接下来m行,每行的格式为M i K B或者Q l r x。

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

对于每个Q操作,输出一行答案。

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

1825
17
978
98

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

1 <= n, m <= 200,0000 <= k, b, x < 1000,000,007

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

线段树裸题

c++:

pascal:

 

[bzoj 4499] 线性函数