题目

题目描述

小C最近在学习线性函数，线性函数可以表示为：$f(x) = kx + b$。现在小C面前有$n$个线性函数$f_i=k_ix+b_i$，他对这$n$个线性函数执行$m$次操作，每次可以：

M i K B代表把第$i$个线性函数改为$f_i(x)=Kx+B$
Q l r x返回$f_r(f_{r-1}(\cdots \cdots f_l(x)))mod(10^9+7)$
输入格式
第一行两个整数$n, m (1 \leqslant n, m \leqslant 200,000)$
接下来$n$行，每行两个整数$k_i, b_i$
接下来$m$行，每行的格式为M i K B或者Q l r x
输出格式
对于每个Q操作，输出一行答案
样例
样例输入
1
2
3
4
5
6
7
8
9
10
11
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
样例输出
1
2
3
4
1825
17
978
98
数据范围与提示
$20\%$：$n, m \leqslant 1000$
另外$10\%$：$b = 0$
另外$10\%$：$k = 1$
$100\%$：$1 \leqslant n, m \leqslant 200,000，0 \leqslant k, b, x < 10^9+7$
来源
FJWC2016 day5
题解
这一题一眼看过去就是线段树，问题是要储存什么
假设现在有两个函数$f_1(x)=k_1x+b_1,f_2(x)=k_2x+b_2$，那么$f(x)=f_2(f_1(x))$的表达式是什么呢？
$f(x)=f_2(f_1(x))=f_2(k_1x+b_1)=k_2(k_1x+b_1)+b_2=k_1k_2x+b_1k_2+b_2$
所以，我们令$k_1k_2=K,b_1k_2+b_2=B$，就可以把$f(x)$表示为$Kx+B$了
所以，我们只需要在线段树中存储这个函数的$k$和$b$，上传时按照上面的方法操作就可以了
注意：线段树要开4倍！！！要记得mod10^9+7！！！
附上代码：
```cpp
include
include
using namespace std;
define l(x) t[x].l
define r(x) t[x].r
define k(x) t[x].k
define b(x) t[x].b
struct Segment_Tree
{
int l,r;
long long k,b;
}t[800010];
int n,m;
long long x,y,z,MOD=1e9+7,k[200010],b[200010];
void build(int p,int l,int r)
{
l(p)=l,r(p)=r;
if(l==r){k(p)=k[l],b(p)=b[l];return;}
int mid=(l+r)>>1;
build(2p,l,mid);
build(2p+1,mid+1,r);
k(p)=k(2p)k(2p+1)%MOD,b(p)=(b(2p)k(2p+1)%MOD+b(2p+1))%MOD;
}
void change(int p,int x,long long K,long long B)
{
if(l(p)==r(p)&&l(p)==x){k(p)=K,b(p)=B;return;}
int mid=(l(p)+r(p))>>1;
if(x<=mid) change(2p,x,K,B);
else change(2p+1,x,K,B);
k(p)=k(2p)k(2p+1)%MOD,b(p)=(b(2p)k(2p+1)%MOD+b(2p+1))%MOD;
}
pair
ask(int p,int L,int R)
{
if(L<=l(p)&&r(p)<=R) return make_pair(k(p),b(p));
int mid=(l(p)+r(p))>>1;
pair
ansl=make_pair(1,0),ansr=make_pair(1,0);
if(L<=mid) ansl=ask(2p,L,R);
if(R>mid) ansr=ask(2p+1,L,R);
return make_pair(ansl.firstansr.first%MOD,(ansl.secondansr.first%MOD+ansr.second)%MOD);
}
int main()
{
scanf(“%d%d”,&n,&m);
for(int i=1;i<=n;i++) scanf(“%lld%lld”,&k[i],&b[i]);
build(1,1,n);
for(int i=1;i<=m;i++){
```
 char op[2];
 scanf("%s %lld%lld%lld",op,&x,&y,&z);
 if(op[0]=='M') change(1,x,y,z);
 else{
     pair<long long,long long> ans;
     ans=ask(1,x,y);
     printf("%lld\n",(ans.first*z%MOD+ans.second)%MOD);
 }
```
}
}

题目

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示

来源

题解

include

include

define l(x) t[x].l

define r(x) t[x].r

define k(x) t[x].k

define b(x) t[x].b