题目

题目描述

小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操作，输出一行答案
样例
样例输入
```
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
```
数据范围与提示
$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！！！
附上代码：

#include<algorithm>
#include<cstdio>
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(2*p,l,mid);
    build(2*p+1,mid+1,r);
    k(p)=k(2*p)*k(2*p+1)%MOD,b(p)=(b(2*p)*k(2*p+1)%MOD+b(2*p+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(2*p,x,K,B);
    else change(2*p+1,x,K,B);
    k(p)=k(2*p)*k(2*p+1)%MOD,b(p)=(b(2*p)*k(2*p+1)%MOD+b(2*p+1))%MOD;
}
pair<long long,long long> 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<long long,long long> ansl=make_pair(1,0),ansr=make_pair(1,0);
    if(L<=mid) ansl=ask(2*p,L,R);
    if(R>mid) ansr=ask(2*p+1,L,R);
    return make_pair(ansl.first*ansr.first%MOD,(ansl.second*ansr.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);
        }
    }
}