线性函数

　　时间限制：2s 内存限制：256mb

问题描述：
小C最近在学习线性函数，线性函数可以表示为：f(x) = kx + b。现在小C面前有n个线性函数，他对这n个线性函数执行m次操作，每次可以：
1.M i K B 代表把第i个线性函数改为：。
2.Q l r x 返回 mod 。

输入格式：
第一行两个整数n, m (1 <= n, m <= 200,000)。
接下来n行，每行两个整数ki, bi。
接下来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 <= 1000
另外10% ：b = 0
另外10% ：k = 1
100%：1 <= n, m <= 200,000，0 <= k, b, x < 1000,000,007

题解：　　

　　考虑到三个线性函数 k1 * x + b1，k2 * x + b2，k3 * x + b3。　　

　　先复合前两个函数，后复合第三个函数的结果是：k3*(k2*(k1*x+b1)+b2)+b3=k1*k2*k3*x+b1*k2*k3+b2*k3+b3。

　先复合后两个函数：k3(k2*x+b2)+b3=k2*k3*x+b2*k3+b3，再复合第一个函数：k1*k2*k3*x+b1*k2*k3+b2*k3+b3。
　　两个结果是一样的，所以函数的复合满足结合律。
　　或者用矩阵来证明，线性函数可以用一个矩阵来表示，而矩阵乘法是具有结合律的，所以线性函数的复合也满足结合律。
有了上述性质，就可以利用线段树维护区间的复合函数，这样就可以在时间内算出答案。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 using namespace std;
10 typedef long long LL;
11 const LL mod=1e9+7,maxn=200010;
12 LL N,M,k[maxn],b[maxn];
13 char s[10];
14 struct Tree{
15     LL l,r,k,b;
16     Tree(){ k=1; b=0; }
17 }T[maxn*10];
18 inline Tree unionn(Tree x,Tree y){
19     Tree ans;
20     ans.k=(x.k*y.k)%mod; ans.b=((x.b*y.k)%mod+y.b)%mod;
21     return ans;
22 }
23 inline void update(LL rt){
24     T[rt].k=(T[rt<<1].k*T[rt<<1|1].k)%mod;
25     T[rt].b=((T[rt<<1].b*T[rt<<1|1].k)%mod+T[rt<<1|1].b)%mod;
26 }
27 inline void build(LL rt,LL l,LL r){
28     T[rt].l=l; T[rt].r=r;
29     if(l==r){
30         T[rt].k=k[l]%mod; T[rt].b=b[l]%mod;
31         return ;
32     }
33     LL mid=(l+r)>>1;
34     build(rt<<1,l,mid);
35     build(rt<<1|1,mid+1,r);
36     update(rt);
37 }
38 inline void change(LL rt,LL pos,LL K,LL B){
39     if(T[rt].l==T[rt].r){
40         T[rt].k=K; T[rt].b=B;
41         return ;
42     }
43     LL mid=(T[rt].l+T[rt].r)>>1;
44     if(pos<=mid) change(rt<<1,pos,K,B);
45     else change(rt<<1|1,pos,K,B);
46     update(rt);
47 }
48 inline Tree query(LL rt,LL l,LL r){
49     if(l<=T[rt].l&&T[rt].r<=r){
50         return T[rt];
51     }
52     LL mid=(T[rt].l+T[rt].r)>>1;
53     Tree ans;
54     if(l<=mid) ans=unionn(ans,query(rt<<1,l,r));
55     if(mid+1<=r) ans=unionn(ans,query(rt<<1|1,l,r));
56     return ans;
57 }
58 int main(){
59 //    freopen("func.in","r",stdin);
60 //    freopen("func.out","w",stdout);
61     scanf("%lld%lld",&N,&M);
62     for(int i=1;i<=N;i++) scanf("%lld%lld",&k[i],&b[i]);
63     build(1,1,N);
64     while(M--){
65         LL x,y,z;
66         scanf("%s%lld%lld%lld",s,&x,&y,&z);
67         if(s[0]=='Q'){
68             Tree tmp=query(1,x,y);
69             LL ans=((tmp.k*z)%mod+tmp.b)%mod;
70             printf("%lld
",ans);
71         }
72         else change(1,x,y,z);
73     }
74     return 0;
75 }